Objetivo

Ordene una lista de elementos para asegurarse de que cada elemento aparezca después de sus dependencias especificadas.

Entrada

Una matriz de matrices de enteros, donde cada entero especifica el índice basado en 0 o en 1 de otro elemento que este elemento debe seguir. La entrada puede ser una matriz o cadena o cualquier otra cosa legible por humanos.

Por ejemplo, una entrada basada en 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
]

Suponga que no hay dependencias circulares, siempre hay al menos un pedido válido.

Salida

Los números en orden de dependencia. Un orden ambiguo no tiene que ser determinista. La salida puede ser una matriz o texto o cualquier otra cosa legible por humanos.

Solo se debe dar un pedido en la salida, incluso cuando hay varios pedidos válidos.

Las salidas posibles para la entrada anterior incluyen:

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

Puntuación

Una función o programa que completa esto en el menor número de bytes gana la gloria de la aceptación. La fecha límite es en 6 días.

Jalea, 8 bytes

ịÐL³ŒḊ€Ụ

Esto se basa en el enfoque de profundidad (no implementado) de la respuesta Python de @ xnor .

Pruébalo en línea!

Cómo funciona

ịÐ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 bytes

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?

Prueba:

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

Python 2, 73 bytes

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

Ordena los vértices por su recuento descendiente, que se fcalcula de forma recursiva. Si un vértice apunta a otro vértice, sus descendientes incluyen el vértice puntiagudo y todos los descendientes de ese vértice, por lo que tiene estrictamente más descendientes. Por lo tanto, se coloca más tarde que el vértice puntiagudo en el orden, como se desee.

El recuento descendiente de un vértice es uno por sí mismo, más el recuento descendiente de cada uno de sus hijos. Tenga en cuenta que un descendiente se puede contar varias veces si hay varias rutas que conducen a él.

También habría funcionado con la profundidad utilizada en lugar del recuento de descendientes

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

excepto que maxtendría que dar 0en una lista vacía.

Pyth, 19 bytes

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

Pruébelo en línea: demostración

Explicación:

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 bytes

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

Ejecución de ejemplo

La E / S está indexada en 1. Cada matriz va en una línea separada, con espacios en blanco como separador de elementos.

$ 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

Cómo funciona

tsort- que aprendí en la respuesta de @ DigitalTrauma - lee pares de tokens, separados por espacios en blanco, que indican un orden parcial, e imprime un orden total (en forma de una lista ordenada de todos los tokens únicos) que extiende el orden parcial mencionado anteriormente.

Todos los números en una línea específica van seguidos de un espacio o un salto de línea. La s/\s/ $. /gparte del comando Perl reemplaza esos caracteres de espacios en blanco con un espacio, el número de línea y otro espacio, asegurándose de que cada n en la línea k precede a k .

Finalmente, si la línea está vacía (es decir, consiste solo en un s/^$/ /salto de línea), le antepone un espacio. De esta manera, la segunda sustitución convierte una línea vacía k en k k, asegurándose de que cada número entero ocurra al menos una vez en la cadena que se canaliza 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

Ingrese como líneas separadas por espacios, por ejemplo:

2
0 3

2

• nl agrega índices basados ​​en cero a todas las líneas
• sed divide las listas de dependencias en pares de dependencias simples y hace que las dependencias incompletas dependan de sí mismas.
• tsort hace el tipo topológico requerido
• tac pone la salida en orden inverso

Ideona Ideone con el caso de prueba de @Dennis

Python 2, 143 118 116 bytes

Un enfoque un poco más aleatorio .

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

Ediciones:

• lo arregló y en realidad también guardó algunos bytes.
• Guardado 2 bytes (gracias @Dennis)