Sort items based on dependency

Question

Goal

Sort a list of items ensuring that each item is listed after its specified dependencies.

Input

An array of arrays of integers, where each integer specifies the 0-based or 1-based index of another item that this item must come after. The input may be an array or string or anything else human readable.

For example, a 0-based input:

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

Assume there are no circular dependencies, there is always at least one valid order.

Output

The numbers in order of dependency. An ambiguous order does not have to be deterministic. The output may be an array or text or anything else human readable.

Only one order should be given in the output, even where there are multiple valid orders.

Possible outputs for the above input include:

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

Scoring

A function or program that completes this in the least number of bytes wins the glory of acceptance. The deadline is in 6 days.

Answer 1

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?

Test:

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

Answer 2

Python 2, 73 bytes

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

Sorts the vertices by their descendant count, which f computes recursively. If a vertex points to another vertex, its descendants include the pointed vertex and all of that vertex's descendants, so it has strictly more descendants. So, it is placed later than the pointed vertex in the ordering, as desired.

The descendant count of a vertex is one for itself, plus the descendant counts of each of its children. Note that a descendant can be counted multiple times if there are multiple paths leading to it.

It would have also worked to used depth rather than descendant count

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

except the max would need to give 0 on an empty list.

Answer 3

Jelly, 8 bytes

ịÐL³ŒḊ€Ụ

This is based on the (unimplemented) depth approach from @xnor's Python answer.

Try it online!

How it works

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

Answer 4

Pyth, 19 bytes

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

Try it online: Demonstration

Explanation:

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

Answer 5

Bash + perl, 35 bytes

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

Example run

I/O is 1-indexed. Each array goes on a separate line, with whitespace as item separator.

$ 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

How it works

tsort – which I learned about in @DigitalTrauma's answer – reads pairs of tokens, separated by whitespace, that indicate a partial ordering, and prints a total ordering (in form of a sorted list of all unique tokens) that extends the aforementioned partial ordering.

All numbers on a specific line are followed by either a space or a linefeed. The s/\s/ $. /g part of the Perl command replaces those whitespace characters with a space, the line number, and another space, thus making sure that each n on line k precedes k.

Finally, if the line is empty (i.e., consists only of a linefeed), s/^$/ / prepends a space to it. This way, the second substitution turns an empty line k into k k, making sure that each integer occurs at least once in the string that is piped to tsort.

Answer 6

Bash + coreutils, 20 80

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

Input as space-separated lines, e.g.:

2
0 3

2

• nl adds zero-based indices to all lines
• sed splits depedency lists into simple dependency pairs, and makes incomplete dependencies dependent on themselves.
• tsort does the required topological sort
• tac puts the output reverse order

Ideone. Ideone with @Dennis' testcase

Answer 7

Python 2, 143 118 116 bytes

A slightly more random approach.

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

Edits:

• fixed it, and actually saved some bytes too.
• Saved 2 bytes (thanks @Dennis)