# 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.

• This is called Topological Sorting for the curious. Mar 18, 2016 at 2:58
• The input may be an array or string or anything else human readable Just to make sure: can it be a 2D array with zeros and ones, where one indicates dependency and zero indicates no dependency? Mar 18, 2016 at 15:03
• @DonMuesli, sorry for the late reply, but no. The idea came from code dependencies. If you added another code module, it would be irresponsible to have to modify irrelevant code modules to declare they were not dependant on this new module. Mar 27, 2016 at 13:09
• That totally makes sense. Shouldn't Dennis be the winner? Mar 27, 2016 at 13:25
• Yes, he is. Sorry, late stressful night and rushing based on assumptions. Mar 27, 2016 at 21:23

## 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:

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. • Right, ok. I think you groked tsort better/faster than I did :) Thanks for the extra explanation. Mar 18, 2016 at 18:24 # 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

# Python 2, 143118 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)