Biorąc pod uwagę listę indeksów i zero lub więcej list liczb całkowitych, wypisz listy liczb całkowitych, posortowane w porządku rosnącym, z kluczowym priorytetem od pierwszego wejścia.

Przykład

Niech wpisane zostaną klucze [1, 0, 2], a listy będą [[5, 3, 4], [6, 2, 1], [5, 2, 1]]. Listy te należy posortować według drugiego elementu, następnie pierwszego elementu, a następnie trzeciego elementu, w porządku rosnącym:

1. Najpierw sortujemy według wartości w indeksie 1:[[6, 2, 1], [5, 2, 1], [5, 3, 4]]
2. Następnie zrywamy wszelkie powiązania z pierwszego sortowania, używając wartości w indeksie 0:[[5, 2, 1], [6, 2, 1], [5, 3, 4]]
3. Na koniec zrywamy wszelkie pozostałe więzi z vlues na indeksie 2(to tak naprawdę nic nie zmienia, ponieważ nie ma już żadnych więzi).

Detale

• Sortowanie jest stabilne: jeśli dwa elementy są równe w odniesieniu do podanych kluczy sortowania, muszą pozostać w tej samej względnej kolejności na wyjściu. Na przykład, jeśli Ai Bsą równe pod danym kluczom sortowania, a dane wejściowe były [..., A, ..., B, ...], Amuszą zostać umieszczone przed Bwyjściem.
• Klawisz sortowania nigdy nie będzie odwoływał się do nieistniejącego elementu na jednej z list wejściowych.
• Żaden klawisz sortowania nie zostanie powtórzony. Dlatego [1, 2, 1]nie jest prawidłową listą kluczy sortowania.
• Żadne elementy, do których nie odnoszą się klucze sortowania, nie uwzględniają kolejności sortowania. Tylko początkowa względna kolejność i wartości elementów, do których odnoszą się klucze sortowania, określają kolejność wyjściową.
• Możesz wybrać, czy klucze sortowania mają być indeksowane zerowo, czy indeksowane jednokrotnie.
• W kluczach sortowania nie będzie żadnych wartości ujemnych. Jeśli zdecydujesz się na użycie jednego indeksowania, w kluczach sortowania nie będzie też zer.
• Wartości całkowite nie przekroczą natywnie reprezentatywnego zakresu twojego języka. Jeśli wybrany język jest natywnie zdolny do liczb całkowitych o dowolnej precyzji (jak Python), wówczas dowolna wartość liczbowa może być obecna na wejściu, z zastrzeżeniem ograniczeń pamięci.

Implementacja referencji (Python 2)

#!/usr/bin/env python

keys = input()
lists = input()

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

Wypróbuj online

Przypadki testowe

Format: keys lists -> output. Wszystkie klucze sortowania są indeksowane od zera.

[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]]

Galaretka , 4 bajty

⁴ị$Þ

Wypróbuj online!

CJam , 13 bajtów

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

Nienazwany blok, który oczekuje listy list i listy priorytetów na górze stosu i zastępuje je posortowaną listą list.

Wypróbuj online! (Jako zestaw testowy.)

Wyjaśnienie

Sortowanie za pomocą przerywników remisu może być realizowane przez wielokrotne sortowanie całej listy w sposób stabilny, od klucza o najniższym priorytecie do klucza o najwyższym priorytecie.

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

Rubin, 35 bajtów

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

Zobacz na eval.in: https://eval.in/652574

Haskell, 38 bajtów

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

Przykład użycia: ( 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 bajtów

SortBy[Extract/@#]&

Wykorzystuje wskaźniki oparte na 1. Ta nienazwana funkcja to curry , więc konwencja wywoływania to:

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

Matematyka SortBymoże wziąć listę funkcji, w którym to przypadku poszczególne funkcje są używane jako kolejne elementy rozstrzygające, więc właśnie tego chcemy. Wszystko, co musimy zrobić, to utworzyć listę funkcji zwracających odpowiedni element listy. Można to zrobić za pomocą Extract. Extractjest zwykle funkcją binarną, Extract[list, index]która zwraca element listy. Jeśli jednak użyje się go jednoznacznie, wówczas Extract[index]zwraca funkcję, która pobiera element indexz z listy do niego przekazanej. Innymi słowy, indexparametr Extractmoże być curry. Korzystamy z tego, mapując Extractlistę podanych nam indeksów, co tworzy listę potrzebnych nam funkcji.

Python, 50 bajtów

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

Jest to wersja implementacji referencyjnej, w której gra się w golfa. lto parametr listy i kparametr kluczy sortowania. lmoże być dowolną iterowalną, o ile jej elementy można indeksować za pomocą liczb całkowitych (takich jak listy, krotki lub dykta z kluczem). kmoże być dowolną iterowalną.

Brachylog , 29 bajtów

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

Wypróbuj online!

Wyjaśnienie

Korzystamy z faktu, że o - Ordermożna użyć z dodatkowym predykatem jako danych wejściowych: porządkujemy listy, używając dla każdej [Keys, a list]listy elementów, a listktóre są indeksowane a keyw kolejności, w jakiej się pojawiają 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 bajtów)

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

Demo online . Jest to anonimowy blok (funkcja), który przyjmuje argumenty w podanej kolejności dla przypadków testowych i pozostawia posortowaną wartość na stosie. Opiera się na wbudowanym rodzaju$ stabilności , ale oficjalny tłumacz gwarantuje to.

Sekcja

{          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 bajtów

]/:{&>

Klucze są indeksowane od zera. LHS to lista kluczy, a RHS to tablica wartości. Ponieważ J nie obsługuje tablic obdartych, każda tablica musi być umieszczona w ramce.

Stosowanie

   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│
└────┴─┴─────────┘

Wyjaśnienie

]/:{&>  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 bajtów

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

Standard ECMAscript nie gwarantuje stabilności sortowania bazowego, więc poniższy 68-bajtowy kod nie przyjmuje takiego założenia:

(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 bajtów

@LDF

Wypróbuj online: pakiet demonstracyjny lub testowy

Dzięki @Maltysen za jeden bajt.

Wyjaśnienie:

@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

Byłem naprawdę zaskoczony, że to zadziałało. To naprawdę dziwna składnia.

JavaScript (ES6) 46

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

Przy każdym porównaniu podczas sortowania skanuj kluczowe indeksy, aby znaleźć właściwą kolejność

Test

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 bajtów

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 nie ma już wbudowanego stabilnego sortowania ; wybranie starszej wersji nie ma możliwości wykonania rekurencyjnego wywołania zwrotnego z wymaganą specyfikacją. Ale nieważne: za pomocą iteratora rekurencyjnego wywołania zwrotnego kosztowałoby mnóstwo; więc nawet nie sprawdziłem, czy to da radę.

Wewnętrzną pętlę można zastąpić inną foreach; zaoszczędziłoby to trochę bajtów podczas wymiany. Ale bez sprawdzenia $b<$a(lub $b<count($i)) spowoduje to nieskończoną pętlę. I dzięki tej kontroli, Theforeach wygrane kosztują tyle samo co zamiana.

Najpierw porównałem rekurencyjnie; ale iteracja oszczędza mnóstwo bajtów:

awaria

// 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 bajtów

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

Wyjaśnienie:

Lista list jest najlepiej reprezentowana jako data.frame w 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

Jeśli lista indeksów jest il (indeksowanie jest od 1):

il = list(1, 2, 3)

Sortowania można dokonać za pomocą następującego kodu:

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

Wynik:

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 bajtów

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

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

Rakieta 218 bajtów

(λ(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)

Niegolfowany (il = lista indeksów; ll = lista list; qsl = szybkie sortowanie listy list; h = głowa (pierwszy element); t = ogon (pozostałe lub pozostałe elementy); g = modyfikowalny filtr 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))

Testowanie:

(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]])

Wynik:

'((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 bajtów

skorzystaj z nowego operatora statku kosmicznego i 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);

Zamiast tego $x[$k[$i]]<=>$y[$k[$i]]możesz używać $x[$k[$i]]-$y[$k[$i]]w wersji PHP większej 7 - 2 bajtów

wersja z własnym indeksem 197 bajtów jak w prawdziwej bibliotece

<?$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 bajtów

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

Ładnie sort-byjest stabilny i umie sortować wektory, a wektory mogą działać jako funkcje. ([4 6 9 7] 2)jest 9(indeksowanie 0).