Étant donné une liste d'indices et zéro ou plusieurs listes d'entiers, affichez les listes d'entiers, triées par ordre croissant, avec la priorité de clé à partir de la première entrée.

Exemple

Soit l'entrée des clés [1, 0, 2]et l'entrée des listes [[5, 3, 4], [6, 2, 1], [5, 2, 1]]. Ces listes doivent être triées par leur deuxième élément, puis le premier élément, puis le troisième élément, dans l'ordre croissant:

1. Tout d'abord, nous trions par les valeurs à l'index 1:[[6, 2, 1], [5, 2, 1], [5, 3, 4]]
2. Ensuite, nous rompons tous les liens du premier tri en utilisant les valeurs à index 0:[[5, 2, 1], [6, 2, 1], [5, 3, 4]]
3. Enfin, nous rompons tous les liens restants avec les valeurs à l'index 2(cela ne change en fait rien, car il n'y a plus de liens).

Détails

• Le tri est stable: si deux éléments se comparent égaux par rapport aux clés de tri données, ils doivent rester dans le même ordre relatif dans la sortie. Par exemple, si Aet Bsont égaux sous les clés de tri données, et que l'entrée était [..., A, ..., B, ...], Adoit être placée avantB dans la sortie.
• Une clé de tri ne fera jamais référence à un élément inexistant dans l'une des listes d'entrée.
• Aucune clé de tri ne sera répétée. Ainsi, [1, 2, 1]n'est pas une liste valide de clés de tri.
• Les éléments non référencés par les clés de tri ne sont pas pris en compte dans l'ordre de tri. Seuls l'ordre relatif initial et les valeurs des éléments référencés par les clés de tri déterminent l'ordre de sortie.
• Vous pouvez choisir si les clés de tri sont indexées zéro ou un indexées.
• Il n'y aura pas de valeurs négatives dans les clés de tri. Si vous choisissez d'utiliser une seule indexation, il n'y aura pas non plus de zéros dans les clés de tri.
• Les valeurs entières ne dépasseront pas la plage représentable nativement de votre langue. Si votre langue choisie est nativement capable d'entiers de précision arbitraire (comme Python), alors n'importe quelle valeur entière peut être présente dans l'entrée, sous réserve des contraintes de mémoire.

Implémentation de référence (Python 2)

#!/usr/bin/env python

keys = input()
lists = input()

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

Essayez-le en ligne

Cas de test

Format: keys lists -> output. Toutes les clés de tri sont indexées zéro.

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

Gelée , 4 octets

⁴ị$Þ

Essayez-le en ligne!

CJam , 13 octets

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

Un bloc sans nom qui attend la liste des listes et la liste des priorités en haut de la pile et les remplace par la liste triée des listes.

Essayez-le en ligne! (En tant que suite de tests.)

Explication

Le tri avec des bris d'égalité peut être mis en œuvre en triant de manière répétée la liste entière en passant de manière stable de la clé de priorité la plus basse à la clé de priorité la plus élevée.

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

Rubis, 35 octets

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

Voir sur eval.in: https://eval.in/652574

Haskell, 38 octets

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

Exemple d'utilisation: ( 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 octets

SortBy[Extract/@#]&

Utilise des indices basés sur 1. Cette fonction sans nom est curry , donc la convention d'appel est:

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

Mathematica SortBypeut prendre une liste de fonctions, auquel cas les fonctions individuelles sont utilisées en tant que bris d'égalité successifs, c'est donc exactement ce que nous voulons. Tout ce que nous devons faire est de créer une liste de fonctions qui renvoient l'élément de liste correspondant. Cela peut être fait avec Extract. Extractest normalement une fonction binaire Extract[list, index]qui renvoie un élément de liste. Cependant, s'il est utilisé de façon unitaire, Extract[index]renvoie une fonction qui récupère l'élément at à indexpartir d'une liste qui lui est passée. En d'autres termes, le indexparamètre de Extractpeut être curry. Nous utilisons cela en mappant Extractsur la liste des indices qui nous est donnée, ce qui crée la liste des fonctions dont nous avons besoin.

Python, 50 octets

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

Il s'agit d'une version trivialement golfée de l'implémentation de référence. lest le paramètre lists et kle paramètre sort keys. lpeut être n'importe quel itérable, tant que ses éléments sont indexables par des entiers (comme des listes, des tuples ou des dict à clé int). kpeut être tout itérable.

Brachylog , 29 octets

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

Essayez-le en ligne!

Explication

Nous utilisons o - Orderen entrée le fait de pouvoir être utilisé avec un prédicat supplémentaire: nous ordonnons les listes en utilisant pour chacune [Keys, a list]la liste des éléments a listdont l'index esta key dans l'ordre dans lequel ils apparaissent 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 octets)

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

Démo en ligne . Il s'agit d'un bloc (fonction) anonyme qui prend les arguments dans l'ordre donné pour les cas de test et laisse la valeur triée sur la pile. Il repose sur le tri intégré$ stabilité du , mais l'interprète officiel le garantit.

Dissection

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

]/:{&>

Les clés sont indexées zéro. Le LHS est la liste des clés et le RHS est un tableau de valeurs. Étant donné que J ne prend pas en charge les tableaux irréguliers, chaque tableau doit être encadré.

Usage

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

Explication

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

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

La norme ECMAscript ne garantit pas que le tri sous-jacent est stable, donc le code de 68 octets suivant ne fait pas cette hypothèse:

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

@LDF

Essayez-le en ligne: démonstration ou suite de tests

Merci à @Maltysen pour un octet.

Explication:

@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

J'ai été vraiment surpris que cela fonctionne. C'est une syntaxe vraiment étrange.

JavaScript (ES6) 46

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

À chaque comparaison pendant le tri, scannez les indices clés pour trouver le bon ordre

Tester

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 octets

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 n'a plus de tri stable intégré ; en choisissant une ancienne version, il n'y a aucun moyen de faire un rappel récursif avec la spécification requise. Mais peu importe: utiliser l' itérateur de rappel récursif coûterait des tonnes; donc je n'ai même pas vérifié si cela pouvait le faire.

La boucle intérieure pourrait être remplacée par une autre foreach; cela permettrait d'économiser quelques octets sur l'échange. Mais sans vérification $b<$a(ou $b<count($i)), cela se traduira par une boucle infinie. Et avec ce chèque, leforeach coûts autant que l'échange gagne.

J'ai d'abord fait la comparaison récursivement; mais l'itération économise des tonnes d'octets:

panne

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

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

Explication:

La liste des listes est mieux représentée comme un data.frame dans 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

Si la liste d'index est il (l'indexation est de 1):

il = list(1, 2, 3)

Le tri peut être effectué avec le code suivant:

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

Production:

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 octets

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

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

Raquette 218 octets

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

Non golfé (il = liste d'index; ll = liste de listes; qsl = tri rapide pour la liste de listes; h = head (premier élément); t = tail (reste ou éléments restants); g = filtre modifiable 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))

Essai:

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

Production:

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

utiliser le nouvel opérateur de vaisseau spatial et 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);

Au lieu de $x[$k[$i]]<=>$y[$k[$i]]vous pouvez utiliser$x[$k[$i]]-$y[$k[$i]] sous une version PHP supérieure 7 - 2 octets

version avec créer un index propre 197 octets comme dans une vraie bibliothèque

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

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

Nicely sort-byest stable et sait trier les vecteurs, et les vecteurs peuvent fonctionner comme des fonctions. ([4 6 9 7] 2)is 9(indexation basée sur 0).