Permutations subject to partial orders

Question

I have two partial orders s_1 and s_2 of natural numbers. How to compute the possible permutations of the numbers of the two sets following the partial orders. We suppose that the two orders are compatible.

For example:

s_1=(1, 2, 4)

s_2=(2,3)

In this example, we search the number of permutations of the numbers from 1, 2, 3 and 4 following the orders in s_1 and s_2.

I would appreciate any suggestions for the general case.

Answer 1

Supposing the partial orderings are compatible, you can split them into binary relations. Your example would become:

s_1 = (1,2)
s_2 = (2,3)
s_3 = (2,4)

You can write an algorithm to traverse all legal orderings from this information. A simple approach would be to recursively search through the available choices of the partially ordered set. Here is an example pseudocode:

Recursive Search For All Legal Permutations Subject to Partial Ordering

1:  procedure FindPOPerms(Poset)
2:  MinNode = minimum value in Poset
3:  MaxNode = maximum value in Poset
3:  Available = MinNode→MaxNode
4:  NNodes = No. of elements in Available
5:  NPoset = No. of rows in Poset
6:  Sequence =  column array of zeros with length NNodes
7:  Candidates = difference between Available set and column 2 of Poset
8:  Selection = Candidates(1)
9:  Available = set difference between Available and Selection
10: Poset = all Poset rows where column 1 is not equal to Selection
11: Iter = 0
12: POPerms  = POPermSearch(Available, Candidates, Poset, Iter, Sequence)
13: end procedure

14: procedure   POPermSearch(Available, Candidates, Poset, Iter, Sequence)
15: Iter = Iter+1
16:     POPerms = empty array
17: if Available is not empty then
18:     for i=1→number of elements in Candidates
19:         S = Candidates(i)
20:         A = set difference between Available  and S
21:         P = all Poset rows where column 1 is not equal to S
22:         C = set difference between A and column 2 of P
23:         Seq = Sequence
24:         Seq(Iter) = S
25:         POP = POPermSearch(A, C, P, Iter, Seq) 
26:         POPerms = add POP as new row to POPerms
27:         end for
28: else
29:     POPerms = Sequence
30: end if
31: end procedure

The input Poset for your case would be a 3x2 array:

1	2
2	3
2	4

with POPerms 2x4 output array:

1	2	3	4
1	2	4	3