生成所有大小为 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)))。