Sort items based on dependency
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]
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.
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