Topographical sorting

John intrepidus at gmail.com
Mon Feb 11 06:10:09 CET 2008


I'm working on a project involving the topographical sorting of partially
ordered sets (posets), using the poset (S, |), where S is the set of
integers <= n. Ultimately, I need to determine all possible topographical
sorts for whatever n happens to be. This requires me to be able to build the
ordered set and then traverse it. The majority of my work is done, and I am
now stuck on figuring out how to determine the number of total sorts
possible. If you are unfamiliar with posets, here is a quick bit of
information about them:

Say that n=6. This means my set of data is {1, 2, 3, 4, 5, 6}. My condition
is |, or the divisor symbol. So I would construct my set with the following
relationship:

1 has all primes as its neighbors
2 divides 4 and 6
3 divides 6

1 does not divide 4 or 6, as posets are transitive, meaning if 1/2 and 2/4,
then it can be said that 1/4. This can be much better represented in this
simple diagram: http://i26.tinypic.com/2ywejwo.jpg

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.

If anyone can offer me some guidance as to where to go from here, it would
be greatly appreciated.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20080211/2e6bb1fe/attachment.html>


More information about the Python-list mailing list