Diberikan daftar indeks dan nol atau lebih daftar bilangan bulat, mengeluarkan daftar bilangan bulat, diurutkan dalam urutan naik, dengan prioritas utama dari input pertama.

Contoh

Biarkan kunci input menjadi [1, 0, 2], dan input daftar menjadi [[5, 3, 4], [6, 2, 1], [5, 2, 1]]. Daftar itu perlu diurutkan berdasarkan elemen kedua, lalu elemen pertama, lalu elemen ketiga, dalam urutan menaik:

1. Pertama, kami mengurutkan berdasarkan nilai pada indeks 1:[[6, 2, 1], [5, 2, 1], [5, 3, 4]]
2. Selanjutnya, kami memutuskan ikatan apa pun dari pengurutan pertama menggunakan nilai pada indeks 0:[[5, 2, 1], [6, 2, 1], [5, 3, 4]]
3. Akhirnya, kami memutuskan ikatan yang tersisa dengan lem pada indeks 2(ini sebenarnya tidak mengubah apa pun, karena tidak ada ikatan yang tersisa).

Detail

• Penyortiran stabil: jika dua elemen membandingkan sama sehubungan dengan kunci penyortiran yang diberikan, mereka harus tetap dalam urutan relatif yang sama dalam output. Misalnya, jika Adan Bsama dengan tombol sortir yang diberikan, dan input tadi [..., A, ..., B, ...], Aharus ditempatkan sebelumnya Bdi output.
• Kunci sortir tidak akan pernah merujuk elemen yang tidak ada di salah satu daftar input.
• Tidak ada tombol sortir yang akan diulang. Dengan demikian, [1, 2, 1]bukan daftar kunci pengurutan yang valid.
• Elemen apa pun yang tidak direferensikan oleh kunci pengurutan tidak memperhitungkan faktor dalam urutan pengurutan. Hanya urutan relatif awal dan nilai-nilai elemen yang dirujuk oleh tombol pengurutan menentukan urutan output.
• Anda dapat memilih apakah kunci sortir diindeks nol atau diindeks satu.
• Tidak akan ada nilai negatif dalam kunci sortir. Jika Anda memilih untuk menggunakan satu-pengindeksan, tidak akan ada nol di kunci pengurutan juga.
• Nilai integer tidak akan melebihi rentang yang dapat diwakili secara asli oleh bahasa Anda. Jika bahasa yang Anda pilih secara bawaan mampu menghasilkan bilangan bulat presisi arbitrer (seperti Python), maka nilai bilangan bulat apa pun dapat ditampilkan dalam input, tergantung pada kendala memori.

Implementasi Referensi (Python 2)

#!/usr/bin/env python

keys = input()
lists = input()

print sorted(lists, key=lambda l:[l[x] for x in keys])

Cobalah online

Uji Kasus

Format: keys lists -> output. Semua kunci sortir diindeks nol.

[1, 0, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[5, 2, 1], [6, 2, 1], [5, 3, 4]]
[1, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[6, 2, 1], [5, 2, 1], [5, 3, 4]]
[0, 1] [[1, 2], [2, 1]] -> [[1, 2], [2, 1]]
[1, 0] [[1, 2], [2, 1]] -> [[2, 1], [1, 2]]
[0] [[4], [10, 11, -88], [-2, 7]] -> [[-2, 7], [4], [10, 11, -88]]
[2] [[-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6]] -> [[-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2]]
[2, 1] [[9, 2, -2, -10, -6], [3, -4, -2]] -> [[3, -4, -2], [9, 2, -2, -10, -6]]
[2, 4, 8] [[5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5], [-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3]] -> [[-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3], [5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5]]
[1, 2, 3, 4, 5] [[-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [5, 3, -6, -5, -4, -4, -8, 2], [9, -4, 1, -1, -3, -2], [-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [1, -5, -3, -10, -7, 9, -8, -5, -1], [-9, 4, -1, -1, 2, 4]] -> [[-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -5, -3, -10, -7, 9, -8, -5, -1], [9, -4, 1, -1, -3, -2], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [5, 3, -6, -5, -4, -4, -8, 2], [-9, 4, -1, -1, 2, 4]]
[8, 7, 3, 2, 4, 9, 1] [[8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9]] -> [[10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5]]

Jelly , 4 byte

⁴ị$Þ

Cobalah online!

CJam , 13 byte

{W%{{X=}$}fX}

Blok tanpa nama yang mengharapkan daftar daftar dan daftar prioritas di atas tumpukan dan menggantinya dengan daftar daftar yang diurutkan.

Cobalah online! (Sebagai suite uji.)

Penjelasan

Penyortiran dengan pemutus pengikat dapat diterapkan dengan berulang kali menyortir seluruh daftar secara stabil dari kunci prioritas terendah ke kunci prioritas tertinggi.

W%      e# Reverse priority list.
{       e# For each priority X...
  {     e#   Sort the lists by the result of this block...
    X=  e#     Extract the Xth element from the current list.
  }$
}fX

Ruby, 35 byte

->k,a{a.sort_by{|e|e.values_at *k}}

Lihat di eval.in: https://eval.in/652574

Haskell, 38 byte

import Data.List
sortOn.flip(map.(!!))

Contoh penggunaan: ( sortOn.flip(map.(!!)) ) [2,1] [[9,2,-2,-10,-6], [3,-4,-2]]-> [[3,-4,-2],[9,2,-2,-10,-6]].

Non-pointfree: f k v=sortOn(\x->map(\y->x!!y)k)v.

Mathematica, 22 19 byte

SortBy[Extract/@#]&

Menggunakan indeks berbasis 1. Fungsi yang tidak disebutkan namanya ini dikerjakan , sehingga konvensi pemanggilan adalah:

SortBy[Extract/@#]&[{2, 1, 3}][{{5, 3, 4}, {6, 2, 1}, {5, 2, 1}}]

Mathematica SortBydapat mengambil daftar fungsi yang dalam hal ini fungsi individual digunakan sebagai pemutus hubungan berturut-turut, jadi itulah yang kami inginkan. Yang perlu kita lakukan adalah membuat daftar fungsi yang mengembalikan elemen daftar yang sesuai. Ini bisa dilakukan dengan Extract. Extractbiasanya merupakan fungsi biner Extract[list, index]yang mengembalikan elemen daftar. Namun jika digunakan secara tidak sengaja, maka Extract[index]mengembalikan fungsi yang mengambil elemen di indexdari daftar yang diteruskan ke sana. Dengan kata lain, indexparameter dari Extractdapat dikeringkan. Kami memanfaatkan ini dengan memetakan Extractdaftar indeks yang kami berikan, yang membuat daftar fungsi yang kami butuhkan.

Python, 50 byte

lambda l,k:sorted(l,key=lambda x:[x[y]for y in k])

Ini adalah versi rujukan untuk implementasi referensi yang sifatnya sangat sederhana. ladalah parameter daftar, dan kmerupakan parameter tombol sortir. ldapat berupa apa saja yang dapat diubah, selama elemen-elemennya dapat disubkripsikan oleh bilangan bulat (seperti daftar, tupel, atau dikt kunci int-keyed). kbisa apa saja iterable.

Brachylog , 29 byte

tT,?hg:Tz:{:2f}o:ta
heI,?t:Im

Cobalah online!

Penjelasan

Kami menggunakan fakta yang o - Orderdapat digunakan dengan predikat tambahan sebagai input: kami memesan daftar dengan menggunakan untuk masing [Keys, a list]- masing daftar elemen a listyang ada di indeks a keydalam urutan mereka muncul Keys.

                          Input = [Keys, List of lists]

tT,                       Call the Keys T
   ?hg:T                  Create the list [[T], List of lists]
        z                 Zip [T] with the list of lists
         :{   }o          Order by the output of this predicate
                :ta       Keep only the last element of each sublist in the Output

           :2f            Find all outputs of the predicate below

heI,                      Take a key I
    ?t:Im                 Output is the Ith element of the sublist

CJam (12 byte)

{{1$\f=}$\;}

Demo online . Ini adalah blok anonim (fungsi) yang mengambil argumen dalam urutan yang diberikan untuk kasus uji dan meninggalkan nilai yang diurutkan pada tumpukan. Itu bergantung pada built-in sort$ yang stabil, tetapi juru bahasa resmi menjamin itu.

Pembedahan

{          e# Define a block. Stack: orders values-to-sort
  {        e#   Sort by...
    1$\f=  e#     Copy orders from the stack, and map array lookup
  }$
  \;       e#   Pop the orders to leave just sorted-values
}

J, 6 byte

]/:{&>

Kunci tidak diindeks. LHS adalah daftar kunci dan RHS adalah array nilai. Karena J tidak mendukung array yang tidak rata, setiap array harus dikotak.

Pemakaian

   f =: ]/:{&>
   < 1 0 2
┌─────┐
│1 0 2│
└─────┘
   5 3 4 ; 6 2 1 ; 5 2 1
┌─────┬─────┬─────┐
│5 3 4│6 2 1│5 2 1│
└─────┴─────┴─────┘
   (< 1 0 2) f  5 3 4 ; 6 2 1 ; 5 2 1
┌─────┬─────┬─────┐
│5 2 1│6 2 1│5 3 4│
└─────┴─────┴─────┘
   (< 1 2) f  5 3 4 ; 6 2 1 ; 5 2 1
┌─────┬─────┬─────┐
│6 2 1│5 2 1│5 3 4│
└─────┴─────┴─────┘
   (< 0) f 4 ; 10 11 _88 ; _2 7
┌────┬─┬─────────┐
│_2 7│4│10 11 _88│
└────┴─┴─────────┘

Penjelasan

]/:{&>  Input: keys (LHS), values (RHS)
   {&>  Select from values at each index in keys
]       Get the values
 /:     Sort up the values using the ones selected with the keys

JavaScript (ES6), 55 byte

(k,l)=>k.reduceRight((l,i)=>l.sort((a,b)=>a[i]-b[i]),l)

Standar ECMAscript tidak menjamin bahwa sort yang mendasarinya stabil, sehingga kode 68-byte berikut tidak membuat asumsi itu:

(k,l)=>l.sort(g=(a,b,i=0)=>i<k.length?a[k[i]]-b[k[i]]||g(a,b,i+1):0)

Pyth, 5 4 byte

@LDF

Cobalah online: Demonstrasi atau Test Suite

Terima kasih kepada @Maltysen untuk satu byte.

Penjelasan:

@LDFQ   Q (=input) added implicitly. 
  D     sort a list of lists by
@L         the sublists generated by some indices
   FQ   executes ^ with the the input as parameter

Saya sangat terkejut bahwa ini berhasil. Ini sintaks yang sangat aneh.

JavaScript (ES6) 46

k=>l=>l.sort((a,b)=>k.some(i=>v=a[i]-b[i])&&v)

Pada setiap perbandingan selama pengurutan, pindai indeks kunci untuk menemukan urutan yang tepat

Uji

f=k=>l=>l.sort((a,b)=>k.some(i=>v=a[i]-b[i])&&v)

;`[1, 0, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[5, 2, 1], [6, 2, 1], [5, 3, 4]]
[1, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[6, 2, 1], [5, 2, 1], [5, 3, 4]]
[0, 1] [[1, 2], [2, 1]] -> [[1, 2], [2, 1]]
[1, 0] [[1, 2], [2, 1]] -> [[2, 1], [1, 2]]
[0] [[4], [10, 11, -88], [-2, 7]] -> [[-2, 7], [4], [10, 11, -88]]
[2] [[-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6]] -> [[-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2]]
[2, 1] [[9, 2, -2, -10, -6], [3, -4, -2]] -> [[3, -4, -2], [9, 2, -2, -10, -6]]
[2, 4, 8] [[5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5], [-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3]] -> [[-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3], [5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5]]
[1, 2, 3, 4, 5] [[-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [5, 3, -6, -5, -4, -4, -8, 2], [9, -4, 1, -1, -3, -2], [-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [1, -5, -3, -10, -7, 9, -8, -5, -1], [-9, 4, -1, -1, 2, 4]] -> [[-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -5, -3, -10, -7, 9, -8, -5, -1], [9, -4, 1, -1, -3, -2], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [5, 3, -6, -5, -4, -4, -8, 2], [-9, 4, -1, -1, 2, 4]]
[8, 7, 3, 2, 4, 9, 1] [[8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9]] -> [[10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5]]`
.split('\n').map(row=>{
  var [keys,list,expected]=row.split(/] -?>? ?\[/)
  keys=eval(keys+']');
  list=eval('['+list+']');
  expected=eval('['+expected);
  var result=f(keys)(list);
  var ok=result.join`|`==expected.join`|`;
  console.log(ok?'OK':'KO',keys+' '+list.join`|`+' -> ' +expected.join`|`,ok?'':result.join`|`)
})

PHP, 212 170 byte

function m(&$i,$k){foreach($i as$a=>$y)for($b=-1;++$b<$a;){for($p=0;$p<count($k)&!$r=$i[$b][$x=$k[$p++]]-$i[$b+1][$x];);if($r>0){$s=$i[$b+1];$i[$b+1]=$i[$b];$i[$b]=$s;}}}

PHP tidak memiliki penyortiran yang stabil lagi ; memilih versi yang lebih lama tidak ada cara untuk melakukan panggilan balik rekursif dengan spesifikasi yang diperlukan. Tapi tidak masalah: menggunakan iterator panggilan balik rekursif akan membutuhkan biaya banyak; jadi saya bahkan tidak memeriksa apakah itu bisa melakukannya.

Lingkaran dalam bisa diganti dengan yang lain foreach; yang akan menghemat beberapa byte pada swapping. Tapi tanpa cek$b<$a (atau $b<count($i)), itu akan menghasilkan loop tak terbatas. Dan dengan cek itu, foreachBiaya sebanyak menukarnya menang.

Saya pertama kali melakukan perbandingan secara rekursif; tetapi iterasi menghemat banyak byte:

kerusakan

// bubble sort
function m(&$i,$k)
{
    foreach($i as$a=>$y)
        for($b=-1;++$b<$a;)
        {
            // comparison:
            for($p=0;$p<count($k)                       // loop through keys
                &
                !$r=$i[$b][$x=$k[$p++]]-$i[$b+1][$x]    // while element equals its successor
            ;);
            // if element is larger than its successor, swap them
            if($r>0)
            {
                $s=$i[$b+1];$i[$b+1]=$i[$b];$i[$b]=$s;
            }
        }
}

R 40 byte

for(i in rev(il)){dd=dd[order(dd[,i]),]}

Penjelasan:

Daftar daftar paling baik direpresentasikan sebagai data.frame di R:

ll2 = list(c(5,3,4), c(5,3,7), c(6,2,1), c(6,1,3), c(5,2,1))
dd = data.frame(do.call(rbind, ll2))
dd
      X1 X2 X3
    1  5  3  4
    2  5  3  7
    3  6  2  1
    4  6  1  3
    5  5  2  1

Jika daftar indeks il (pengindeksan adalah dari 1):

il = list(1, 2, 3)

Penyortiran dapat dilakukan dengan kode berikut:

for(i in rev(il)){dd = dd[order(dd[,i]),]}

Keluaran:

dd
  X1 X2 X3
5  5  2  1
1  5  3  4
2  5  3  7
4  6  1  3
3  6  2  1

Perl 6  23 20  19 byte

->\a,\b{b.sort:{.[|a]}}
{$^a;$^b.sort:{.[|$a]}}
{$^b.sort: *.[|$^a]}

{$^b.sort: *[|$^a]}

Racket 218 byte

(λ(il ll)(define qsl(λ(l i)(if(null? l)l(let*((h(first l))(t(rest l))(g(λ(ff)(filter(λ(x)(ff(list-ref x i)
(list-ref h i)))t))))(append(qsl(g <)i)(list h)(qsl(g >=)i))))))(for((i(reverse il)))(set! ll(qsl ll i)))ll)

Tidak tergabung (il = daftar indeks; ll = daftar daftar; qsl = quicksort untuk daftar daftar; h = kepala (elemen pertama); t = ekor (elemen sisa atau yang tersisa); g = filter yang dapat dimodifikasi fn):

(define qsl
  (λ(l i)
    (if (null? l)
        l
        (let* ((h (first l))
               (t (rest  l))
               (g (λ(ff) (filter (λ(x) (ff (list-ref x i) (list-ref h i))) t))))
          (append (qsl (g <) i)
                  (list h)
                  (qsl (g >=) i)
                  )))))
(define f
  (λ(il ll)
    (for ((i (reverse il)))
      (set! ll (qsl ll i)))
    ll))

Pengujian:

(f (list 0 1 2) (list (list 5 3 4) (list 5 3 7) (list 6 2 1) (list 6 1 3) (list 5 2 1)))
(f [list 1 2] [list [list 5 3 4] [list 6 2 1] [list 5 2 3]])

Keluaran:

'((5 2 1) (5 3 4) (5 3 7) (6 1 3) (6 2 1))
'((6 2 1) (5 2 3) (5 3 4))

PHP, 139 Bytes

gunakan operator pesawat ruang angkasa baru dan usort

<?$a=$_GET[a];function c($x,$y,$i=0){$k=$_GET[k];return$x[$k[$i]]-$y[$k[$i]]?:($k[++$i]?c($x,$y,$i):0);}usort($a,c);echo json_encode($a);

Alih-alih $x[$k[$i]]<=>$y[$k[$i]]Anda dapat menggunakan di $x[$k[$i]]-$y[$k[$i]]bawah Versi PHP lebih besar 7 - 2 Bytes

versi dengan membuat indeks 197 Bytes sendiri seperti di perpustakaan nyata

<?$m=min(array_map(min,$a=$_GET[a]));foreach($a as$p=>$v){$k="";foreach($s=$_GET[s]as$f){$k.=str_pad($v[$f]-$m,5,0,0);}$k.=str_pad($p,5,0,0);$r[$k]=$v;}ksort($r);echo json_encode(array_values($r));

Clojure, 29 byte

#(sort-by(fn[c](mapv c %))%2)

Baik sort-bystabil dan tahu cara mengurutkan vektor, dan vektor dapat beroperasi sebagai fungsi. ([4 6 9 7] 2)adalah 9(pengindeksan berbasis 0).