Bei einer gegebenen Liste von Indizes und null oder mehr Listen von ganzen Zahlen geben Sie die Listen von ganzen Zahlen in aufsteigender Reihenfolge mit der Schlüsselpriorität von der ersten Eingabe aus.

Beispiel

Die Tasteneingabe sei [1, 0, 2]und die Listeneingabe sei [[5, 3, 4], [6, 2, 1], [5, 2, 1]]. Diese Listen müssen nach dem zweiten Element, dem ersten Element und dem dritten Element in aufsteigender Reihenfolge sortiert werden:

1. Zuerst sortieren wir nach den Werten am Index 1:[[6, 2, 1], [5, 2, 1], [5, 3, 4]]
2. Als nächstes lösen wir alle Bindungen von der ersten Sortierung unter Verwendung der Werte am Index 0:[[5, 2, 1], [6, 2, 1], [5, 3, 4]]
3. Schließlich brechen wir alle verbleibenden Bindungen zu den Werten am Index 2(dies ändert eigentlich nichts, da keine Bindungen mehr übrig sind).

Einzelheiten

• Die Sortierung ist stabil: Wenn zwei Elemente in Bezug auf die angegebenen Sortierschlüssel gleich sind, müssen sie in der Ausgabe in derselben relativen Reihenfolge bleiben. Wenn z. B. Aund Bunter den angegebenen Sortierschlüsseln gleich sind und die Eingabe war [..., A, ..., B, ...], Amuss sie vor Bder Ausgabe platziert werden.
• Ein Sortierschlüssel verweist niemals auf ein nicht vorhandenes Element in einer der Eingabelisten.
• Es wird kein Sortierschlüssel wiederholt. Es [1, 2, 1]handelt sich also nicht um eine gültige Liste von Sortierschlüsseln.
• Alle Elemente, auf die die Sortierschlüssel nicht verweisen, werden nicht in die Sortierreihenfolge einbezogen. Nur die anfängliche relative Reihenfolge und die Werte der Elemente, auf die die Sortierschlüssel verweisen, bestimmen die Ausgabereihenfolge.
• Sie können wählen, ob die Sortierschlüssel nullindiziert oder einsindiziert sind.
• Die Sortierschlüssel enthalten keine negativen Werte. Wenn Sie sich für die Indizierung mit einem Index entscheiden, werden auch in den Sortierschlüsseln keine Nullen angezeigt.
• Ganzzahlige Werte überschreiten nicht den Bereich, den Ihre Sprache von Haus aus darstellen kann. Wenn die von Ihnen gewählte Sprache von Haus aus Ganzzahlen mit willkürlicher Genauigkeit unterstützt (wie Python), kann ein beliebiger ganzzahliger Wert in der Eingabe vorhanden sein, abhängig von Speicherbeschränkungen.

Referenzimplementierung (Python 2)

#!/usr/bin/env python

keys = input()
lists = input()

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

Probieren Sie es online aus

Testfälle

Format: keys lists -> output. Alle Sortierschlüssel sind nullindiziert.

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

Gelee , 4 Bytes

⁴ị$Þ

Probieren Sie es online!

CJam , 13 Bytes

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

Ein unbenannter Block, der die Liste der Listen und die Liste der Prioritäten über dem Stapel erwartet und durch die sortierte Liste der Listen ersetzt.

Probieren Sie es online! (Als Testsuite.)

Erläuterung

Das Sortieren mit Verbindungsunterbrechern kann implementiert werden, indem die gesamte Liste wiederholt stabil vom Schlüssel mit der niedrigsten Priorität zum Schlüssel mit der höchsten Priorität sortiert wird.

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 Bytes

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

Sehen Sie es auf eval.in: https://eval.in/652574

Haskell, 38 Bytes

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

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

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

Mathematica, 22 19 Bytes

SortBy[Extract/@#]&

Verwendet 1-basierte Indizes. Diese unbenannte Funktion wird curried , so dass die Aufrufkonvention ist:

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

Mathematica's SortBykann eine Liste von Funktionen aufnehmen. In diesem Fall werden die einzelnen Funktionen als aufeinanderfolgende Unterbrecher verwendet, also ist es genau das, was wir wollen. Wir müssen nur eine Liste von Funktionen erstellen, die das entsprechende Listenelement zurückgeben. Dies kann mit erfolgen Extract. Extractist normalerweise eine Binärfunktion, Extract[list, index]die ein Listenelement zurückgibt. Wenn es jedoch nur einmal verwendet wird, wird Extract[index]eine Funktion zurückgegeben, die das Element indexvon einer an sie übergebenen Liste abruft . Mit anderen Worten kann der indexParameter von Extractgewechselt werden. Dies machen Extractwir uns zunutze, indem wir über die Liste der Indizes, die wir erhalten, eine Zuordnung vornehmen , wodurch die Liste der Funktionen erstellt wird, die wir benötigen.

Python, 50 Bytes

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

Dies ist eine einfach zu spielende Version der Referenzimplementierung. list der Parameter lists und kder Parameter sort keys. lkann beliebig iterierbar sein, solange seine Elemente durch ganze Zahlen (wie Listen, Tupel oder int-keyed Dicts) subskriptierbar sind. kkann jede iterable sein.

Brachylog , 29 Bytes

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

Probieren Sie es online!

Erläuterung

Wir verwenden die Tatsache, dass o - Orderein zusätzliches Prädikat als Eingabe verwendet werden kann: Wir ordnen die Listen in der Reihenfolge an, in der sie auftauchen, indem wir für jede [Keys, a list]Liste die Elemente verwenden, a listderen Index am Anfang steht .a keyKeys

                          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 Bytes)

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

Online-Demo . Dies ist ein anonymer Block (eine Funktion), der die Argumente in der angegebenen Reihenfolge für die Testfälle verwendet und den sortierten Wert auf dem Stapel belässt. Es setzt voraus, dass die eingebaute Sorte $stabil ist, aber der offizielle Dolmetscher garantiert dies.

Präparation

{          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 Bytes

]/:{&>

Schlüssel sind mit einem Index von Null versehen. Die LHS ist die Liste der Schlüssel und die RHS ist ein Array von Werten. Da J keine unregelmäßigen Arrays unterstützt, muss jedes Array mit einem Kästchen versehen werden.

Verwendung

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

Erläuterung

]/:{&>  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)

Der ECMAscript-Standard garantiert nicht, dass die zugrunde liegende Sortierung stabil ist, sodass der folgende 68-Byte-Code diese Annahme nicht trifft:

(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 Bytes

@LDF

Probieren Sie es online aus: Demo oder Test Suite

Danke an @Maltysen für ein Byte.

Erläuterung:

@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

Ich war wirklich überrascht, dass dies funktionierte. Es ist eine wirklich seltsame Syntax.

JavaScript (ES6) 46

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

Scannen Sie bei jedem Vergleich während des Sortierens die Schlüsselindizes, um die richtige Reihenfolge zu finden

Prüfung

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 Bytes

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 hat keine stabile Sortierung mehr eingebaut ; Bei einer älteren Version ist es nicht möglich, einen rekursiven Rückruf mit der erforderlichen Spezifikation durchzuführen. Aber vergiss nicht: Die Verwendung des rekursiven Callback-Iterators würde Tonnen kosten. also habe ich nicht mal nachgesehen, ob das klappt.

Die innere Schleife könnte durch eine andere ersetzt werden foreach ; das würde ein paar Bytes beim Tauschen sparen. Ohne ein Häkchen bei $b<$a(oder $b<count($i)) führt dies jedoch zu einer Endlosschleife. Und mit diesem Scheck gewinnen die foreachKosten so viel wie der Tausch.

Ich habe den Vergleich zuerst rekursiv durchgeführt. Aber Iteration spart Tonnen von Bytes:

Nervenzusammenbruch

// 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 Bytes

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

Erläuterung:

Die Liste der Listen wird am besten als data.frame in R dargestellt:

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

Wenn die Indexliste il ist (die Indexierung ist von 1):

il = list(1, 2, 3)

Das Sortieren kann mit folgendem Code erfolgen:

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

Ausgabe:

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 Bytes

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

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

Schläger 218 Bytes

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

Ungolfed (il = Indexliste; ll = Liste der Listen; qsl = Quicksort für Liste der Listen; h = Kopf (erstes Element); t = Schwanz (restliche oder verbleibende Elemente); g = modifizierbarer Filter 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))

Testen:

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

Ausgabe:

'((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

benutze den neuen Raumschiff Operator und benutze 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);

Anstelle von $x[$k[$i]]<=>$y[$k[$i]]Ihnen können verwenden$x[$k[$i]]-$y[$k[$i]] unter einer PHP-Version größere 7 - 2 Bytes verwenden

version mit create a own index 197 Bytes wie in einer echten bibliothek

<?$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 Bytes

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

Schön sort-byist stabil und weiß, wie man Vektoren sortiert, und Vektoren können als Funktionen fungieren. ([4 6 9 7] 2)ist 9(0-basierte Indizierung).