在 python 中生成非交叉分区

Question

我想生成集合 S= [1,2,3,4,...,n] 的所有非交叉分区，其中非交叉分区是不存在元素 a 的分区 < b < c < d where a,c are in the same block, and b,d are in the same but different block.

有人可以帮我吗？

我有一个算法可以执行此操作，但它运行速度非常慢，并且在尝试计算集合 S= [1,2,3,4,...,14] 上的非交叉分区时出现内存错误。

Answer 1

我在下面创建了一个相当优化的实现。请注意，它会改变分区列表（以速度的名义），因此您将需要在生成分区时使用它们，或者对它们进行深度复制。做前者会明显更快，所以如果可能的话选择它。

def make_partitions(elements):
    yield from _make_partitions(sorted(elements, reverse=True), [], []) 

def _make_partitions(elements, active_partitions, inactive_partitions):
    if not elements:
        yield active_partitions + inactive_partitions
        return

    elem = elements.pop()

    # Make create a new partition
    active_partitions.append([elem])
    yield from _make_partitions(elements, active_partitions, inactive_partitions)
    active_partitions.pop()

    # Add element to each existing partition in turn
    size = len(active_partitions)
    for part in active_partitions[::-1]:
        part.append(elem)
        yield from _make_partitions(elements, active_partitions, inactive_partitions)
        part.pop()

        # Remove partition that would create a cross if new elements were added
        inactive_partitions.append(active_partitions.pop())
    
    # Add back removed partitions
    for _ in range(size):
        active_partitions.append(inactive_partitions.pop())

    elements.append(elem)

用法：

for partitions in make_partitions([1, 2, 3, 4, 5]):
    print(partitions)

输出：

[[1], [2], [3], [4], [5]]
[[1], [2], [3], [4, 5]]
[[1], [2], [3, 5], [4]]
[[1], [2, 5], [4], [3]]
[[1, 5], [4], [3], [2]]
[[1], [2], [3, 4], [5]]
[[1], [2], [3, 4, 5]]
[[1], [2, 5], [3, 4]]
[[1, 5], [3, 4], [2]]
[[1], [2, 4], [5], [3]]
[[1], [2, 4, 5], [3]]
[[1, 5], [3], [2, 4]]
[[1, 4], [5], [3], [2]]
[[1, 4, 5], [3], [2]]
[[1], [2, 3], [4], [5]]
[[1], [2, 3], [4, 5]]
[[1], [2, 3, 5], [4]]
[[1, 5], [4], [2, 3]]
[[1], [2, 3, 4], [5]]
[[1], [2, 3, 4, 5]]
[[1, 5], [2, 3, 4]]
[[1, 4], [5], [2, 3]]
[[1, 4, 5], [2, 3]]
[[1, 3], [4], [5], [2]]
[[1, 3], [4, 5], [2]]
[[1, 3, 5], [2], [4]]
[[1, 3, 4], [5], [2]]
[[1, 3, 4, 5], [2]]
[[1, 2], [3], [4], [5]]
[[1, 2], [3], [4, 5]]
[[1, 2], [3, 5], [4]]
[[1, 2, 5], [4], [3]]
[[1, 2], [3, 4], [5]]
[[1, 2], [3, 4, 5]]
[[1, 2, 5], [3, 4]]
[[1, 2, 4], [5], [3]]
[[1, 2, 4, 5], [3]]
[[1, 2, 3], [4], [5]]
[[1, 2, 3], [4, 5]]
[[1, 2, 3, 5], [4]]
[[1, 2, 3, 4], [5]]
[[1, 2, 3, 4, 5]]

如前所述，如果您需要保留分区，则需要 deepcopy 它们：

from copy import deepcopy

results = [deepcopy(partitions) for partitions in make_partitions(list(range(6)))]

在我的机器上，这可以在几秒钟内生成一组 14 个不同元素的所有非交叉分区。