algorithm - 枚举所有偏序

Question

如何有效地枚举有限集上的所有偏序？

我想检查是否存在具有指定属性的部分订单。为了检查这一点，我将用蛮力枚举小型有限集上所有可能的偏序。

Answer 1

为了使您的项目实用，它们必须是非常小的有限集。

具有 n 个标记元素的标记后置集的数量是 Sloane 序列A001035，其值直到 n=18 是已知的：

0 1
1 1
2 3
3 19
4 219
5 4231
6 130023
7 6129859
8 431723379
9 44511042511
10 6611065248783
11 1396281677105899
12 414864951055853499
13 171850728381587059351
14 98484324257128207032183
15 77567171020440688353049939
16 83480529785490157813844256579
17 122152541250295322862941281269151
18 241939392597201176602897820148085023

序列A000112是未标记的序列的数量；不出所料，这些数字较小，但仍迅速增长而遥不可及。他们似乎只知道 n=16；第₁₆页是 4483130665195087。

Gunnar Brinkman 和 Brendan McKay 的论文中有一个算法，列在上面链接的 OEIS A000112 页面上的参考资料中。这项工作是在 2002 年完成的，使用了大约 200 个工作站，计算 4483130665195087 个大小为 16 的未标记数据集大约需要 30 个机器年（参考机器是 1 GHz Pentium III）。今天，它可以做得更快，但 p ₁₇的值大概要大两个十进制数量级。