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:<br>
<br>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:<br><br>1 has all primes as its neighbors<br>2 divides 4 and 6<br>
3 divides 6<br><br>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: <a href="http://i26.tinypic.com/2ywejwo.jpg">http://i26.tinypic.com/2ywejwo.jpg</a><br>
<br>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.<br>
<br>If anyone can offer me some guidance as to where to go from here, it would be greatly appreciated.<br>