Frank Niessink
2/11/2008 8:38:00 PM
Hi John,
2008/2/11, John <intrepidus@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