Objectif

Triez une liste d'éléments en vous assurant que chaque élément est répertorié après ses dépendances spécifiées.

Contribution

Un tableau de tableaux d'entiers, où chaque entier spécifie l'index basé sur 0 ou 1 d'un autre élément que cet élément doit suivre. L'entrée peut être un tableau ou une chaîne ou tout autre élément lisible par l'homme.

Par exemple, une entrée basée sur 0:

[
  [ 2 ],    // item 0 comes after item 2
  [ 0, 3 ], // item 1 comes after item 0 and 3
  [ ],      // item 2 comes anywhere
  [ 2 ]     // item 3 comes after item 2
]

Supposons qu'il n'y ait pas de dépendances circulaires, il y a toujours au moins un ordre valide.

Production

Les nombres par ordre de dépendance. Un ordre ambigu n'a pas à être déterministe. La sortie peut être un tableau ou du texte ou tout autre élément lisible par l'homme.

Une seule commande doit être indiquée dans la sortie, même s'il existe plusieurs commandes valides.

Les sorties possibles pour l'entrée ci-dessus incluent:

[ 2, 3, 0, 1 ]
[ 2, 0, 3, 1 ]

Notation

Une fonction ou un programme qui termine cela dans le moins d'octets gagne la gloire de l'acceptation. Le délai est de 6 jours.

Gelée, 8 octets

ịÐL³ŒḊ€Ụ

Ceci est basé sur l'approche en profondeur (non implémentée) de la réponse Python de @ xnor .

Essayez-le en ligne!

Comment ça fonctionne

ịÐL³ŒḊ€Ụ  Main link. Input: A (list of dependencies)

 ÐL       Apply the atom to the left until a loop is reached, updating the left
          argument with the last result, and the right argument with the previous
          left argument.
ị         For each number in the left argument, replace it with the item at that
          index in the right argument.
   ³      Call the loop with left arg. A (implicit) and right arg. A (³).
    ŒḊ€   Compute the depth of each resulting, nested list.
       Ụ  Sort the indices of the list according to their values.

Pyth, 21 octets

hf.A.e!f>xYTxkTbQ.plQ

                    Q  input
                   l   length of input array
                 .p    all permutations of [0, 1, ..., lQ-2, lQ-1]
hf                     find the first permutation for which...
    .e          Q        map over the input array with indices...
       f       b           find all elements in each input subarray where...
        >xYT                 index of dependency is greater than...
            xkT              index of item
      !                    check whether resulting array is falsy (empty)
  .A                     is the not-found check true for [.A]ll elements?

Tester:

llama@llama:~$ echo '[[2],[0,3],[],[2]]' | pyth -c 'hf.A.e!f>xYTxkTbQ.plQ' 
[2, 0, 3, 1]

Python 2, 73 octets

l=input()
f=lambda n:1+sum(map(f,l[n]))
print sorted(range(len(l)),key=f)

Trie les sommets par leur nombre de descendants, qui fcalcule récursivement. Si un sommet pointe vers un autre sommet, ses descendants incluent le sommet pointé et tous les descendants de ce sommet, il a donc strictement plus de descendants. Ainsi, il est placé plus tard que le sommet pointé dans l'ordre, comme vous le souhaitez.

Le nombre de descendants d'un sommet est un pour lui-même, plus le nombre de descendants de chacun de ses enfants. Notez qu'un descendant peut être compté plusieurs fois s'il y a plusieurs chemins qui y mènent.

Il aurait également fonctionné à la profondeur utilisée plutôt qu'au nombre de descendants

f=lambda n:1+max(map(f,l[n]))

sauf maxqu'il faudrait donner 0sur une liste vide.

Pyth, 19 octets

hf!s-V@LQT+k._T.plQ

Essayez-le en ligne: Démonstration

Explication:

hf!s-V@LQT+k._T.plQ   implicit: Q = input list
               .plQ   all permutations of [0, 1, ..., len(Q)-1]
 f                    filter for permutations T, which satisfy:
      @LQT               apply the permutation T to Q
                         (this are the dependencies)
            ._T          prefixes of T
          +k             insert a dummy object at the beginning
                         (these are the already used elements)
    -V                   vectorized subtraction of these lists
   s                     take all dependencies that survived
  !                      and check if none of them survived
h                    print the first filtered permutation

Bash, 35 octets

perl -pe's/^$/ /;s/\s/ $. /g'|tsort

Exemple d'exécution

Les E / S sont indexées sur 1. Chaque tableau va sur une ligne distincte, avec des espaces comme séparateur d'élément.

$ echo $'4\n1\n\n3\n1 3 2' # [[4], [1], [], [3], [1, 3, 2]]
4
1

3
1 3 2
$ bash tsort <<< $'4\n1\n\n3\n1 3 2'
3
4
1
2
5

Comment ça fonctionne

tsort- que j'ai appris dans la réponse de @ DigitalTrauma - lit des paires de jetons, séparées par des espaces, qui indiquent une commande partielle, et imprime une commande totale (sous la forme d'une liste triée de tous les jetons uniques) qui étend la commande partielle susmentionnée.

Tous les nombres sur une ligne spécifique sont suivis d'un espace ou d'un saut de ligne. La s/\s/ $. /gpartie de la commande Perl remplace ces caractères d'espacement par un espace, le numéro de ligne et un autre espace, s'assurant ainsi que chaque n sur la ligne k précède k .

Enfin, si la ligne est vide (c'est-à-dire ne se compose que d'un saut de ligne), lui s/^$/ /ajoute un espace. De cette façon, la deuxième substitution transforme une ligne vide k en k k, en s'assurant que chaque entier apparaît au moins une fois dans la chaîne qui est dirigée vers tsort.

Bash + coreutils, 20 80

nl -v0 -ba|sed -r ':;s/(\S+\s+)(\S+) /\1\2\n\1 /;t;s/^\s*\S+\s*$/& &/'|tsort|tac

Saisie sous forme de lignes séparées par des espaces, par exemple:

2
0 3

2

• nl ajoute des indices de base zéro à toutes les lignes
• sed divise les listes de dépendances en paires de dépendances simples et rend dépendantes les dépendances incomplètes.
• tsort fait le tri topologique requis
• tac met l'ordre inverse de sortie

Ideone. Ideone avec le testcase de @Dennis

Python 2, 143 118 116 116 octets

Une approche un peu plus aléatoire .

from random import*
l=input()
R=range(len(l))
a=R[:]
while any(set(l[a[i]])-set(a[:i])for i in R):shuffle(a)
print a

Modifications:

• l'a corrigé et a également enregistré quelques octets.
• Enregistré 2 octets (merci @Dennis)