生成大小为n的所有预购/弱订单的算法

Question

我正在寻找一种半有效的算法，给定一个输入集，从中生成所有的总预购关系(或等价地，所有弱订单)。你也可以称之为n个标记元素的所有优先排列。

我已经尝试通过首先生成大小为n的所有排列，然后通过'~'折叠这些排列的子序列来实现这一点，但这是非常低效的，因为有许多重复，而且我也错过了一些结果。大小由富比尼数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> b, c>> b, a ~ c> b, a> c> b, a> b ~ c, c> b>,一个~ ~ b> c, 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)))