1

我正在寻找一种半有效的算法，给定一个输入集，从中生成所有总的预序关系（或者，等效地，所有弱序）。您也可以将其称为 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

4

1 回答 1

4

不是太难。在 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)))。

于 2015-09-21T11:56:28.133 回答