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


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.


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 ]


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

  • 5
    \$\begingroup\$ This is called Topological Sorting for the curious. \$\endgroup\$ Commented Mar 18, 2016 at 2:58
  • \$\begingroup\$ 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? \$\endgroup\$
    – Luis Mendo
    Commented Mar 18, 2016 at 15:03
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Mar 27, 2016 at 13:09
  • \$\begingroup\$ That totally makes sense. Shouldn't Dennis be the winner? \$\endgroup\$
    – Luis Mendo
    Commented Mar 27, 2016 at 13:25
  • \$\begingroup\$ Yes, he is. Sorry, late stressful night and rushing based on assumptions. \$\endgroup\$ Commented Mar 27, 2016 at 21:23

7 Answers 7


Pyth, 21 bytes

                    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?


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

Python 2, 73 bytes

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.

  • 2
    \$\begingroup\$ Beautiful algorithm. This would score 12 bytes in both Pyth and Jelly. \$\endgroup\$
    – Dennis
    Commented Mar 18, 2016 at 21:00

Jelly, 8 bytes


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.
  • \$\begingroup\$ Would these 8 characters actually be 19 bytes? \$\endgroup\$ Commented Mar 27, 2016 at 13:05
  • \$\begingroup\$ @Hand-E-Food Jelly uses a custom encoding (not UTF 8), so each character is a byte \$\endgroup\$
    – Luis Mendo
    Commented Mar 27, 2016 at 13:26
  • \$\begingroup\$ @Hand-E-Food Don Muesli is correct. Jelly uses this code page by default, which encodes all characters it understands as one byte each. \$\endgroup\$
    – Dennis
    Commented Mar 27, 2016 at 14:20

Pyth, 19 bytes


Try it online: Demonstration


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

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

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.

  • \$\begingroup\$ Right, ok. I think you groked tsort better/faster than I did :) Thanks for the extra explanation. \$\endgroup\$ Commented 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.:

0 3

  • 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


Python 2, 143 118 116 bytes

A slightly more random approach.

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


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.