服从偏序的排列

Question

我有两个自然数的偏序s_1和s_2。如何计算遵循偏序的两个集合的数的可能排列。我们假定这两个次序是相容的。

例如：

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

在本例中，我们按照s_1和s_2中的顺序搜索1、2、3和4中的数字的排列数。

如果能就一般情况提出任何建议，我将不胜感激。

Answer 1

假设偏序是兼容的，您可以将它们拆分为二进制关系。你的例子会变成：

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

您可以编写一个算法来遍历此信息中的所有合法排序。一个简单的方法是递归地搜索偏序集的可用选项。下面是一个伪代码示例：

所有服从偏序的合法排列的递归搜索

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

您的案例的输入Poset将是3x2阵列：

1	2
2	3
2	4