Topographical sorting

[Frank Niessink]

Hi John,

2008/2/11, John <intrepidus at gmail.com>:
> Now, on to my problem. Topographical sorting essentially involves removing
> the minimal element in a set (1), and then arbitrarily choosing the next
> minimal element and removing it as well. So, after removing 1, one could
> remove 5, then 2, then 3, then 4, then 6, resulting in the sort of 15234.
> One could also get 123456. There are a number of sorts possible. This is
> where I am currently stuck, attempting to implement an algorithm that finds
> all possible sorts. I have looked at the topographical pseudocode available
> at Wikipedia, but this does not apply - it finds one topographical sort, not
> all.

How about something like this:

def allSorts(set):
    result = []
    for element in smallestElements(set):
        for tail in allSorts(set - element):
            result.append([element] + tail)
    return result

Cheers, Frank