生成所有 preorders/weak 个大小为 n 的订单的算法

Question

我正在寻找一种半途高效的算法，给定一个输入集，从中生成所有总预序关系（或者，等效地，所有弱顺序）。也可以称其为n个标记元素的所有优先排列。

我已经尝试通过首先生成大小为 n 的所有排列，然后用“~”折叠这些排列的子序列来实现这一点，但是由于重复很多，这是非常低效的，而且我也错过了一些结果。大小由 Fubini 编号 1、1、3、13、75、541、4683、47293、545835 ……（OEIS 编号 A000670）给出，并且随着 n 的增加而快速增长。我只需要前几个，比如说，直到 n=8。

示例：对于 A={a, b, c} 且 n=3，结果是 13 个预订单：

b>a>c, b>a~c, b>c>a, b~c>a, c>b>a, c>a~b, c>a>b, a~c >b, a>c>b, a>b~c, a>b>c, a~b>c, a~b~c

Answer 1

不太难。在 Python 3:

import itertools

def weakorders(A):
    if not A:  # i.e., A is empty
        yield []
        return
    for k in range(1, len(A) + 1):
        for B in itertools.combinations(A, k):  # i.e., all nonempty subsets B
            for order in weakorders(set(A) - set(B)):
                yield [B] + order

调用，例如 list(weakorders(range(8)))。

生成所有 preorders/weak 个大小为 n 的订单的算法

Algorithm to generate all preorders/weak orders of size n

algorithm

combinatorics

partial-ordering

oeis