排列 A 框中的 N 个元素？

Question

我正在尝试找到所有可能的方式来排列 A 框中的 N 个元素，其中框的顺序和元素的顺序无关紧要，但哪些元素同时放在一起很重要盒子。例如，3 个框和 3 个元素的预期结果如下：

            box_1       box_2      box_3
case-1      [1,2,3]    []          []
case-2      [1,2]      [3]         []
case-3      [1,3]      [2]         []
case-4      [2,3]      [1]         []
case-5      [1]        [2]         [3]

这是一个类似但比此处提出的问题更普遍的问题：Enumeration of combinations of N balls in A boxes?

我将非常感谢对这个问题的任何贡献，最好使用 python 语言。

Answer 1

这些被称为set partitions. A recursive function can be found here: Set partitions in Python。一个更高效的 "bottom-up" 递归版本是这样的：

def generate_partitions(a):
    a = list(a)
    n = len(a)
    partition = [] # a list of lists, currently empty

    def assign(i):
        if i >= n:
            yield [list(part) for part in partition]
        else:
            # assign a[i] to an existing part
            for part in partition:
                part.append(a[i])
                yield from assign(i + 1)
                part.pop()

            # assign a[i] to a completely new part
            partition.append([a[i]])
            yield from assign(i + 1)
            partition.pop()

    if n:
        yield from assign(0)
    else:
        yield [[]]


for partition in generate_partitions([1,2,3]):
    print(*partition)

输出：

[1, 2, 3]
[1, 2] [3]
[1, 3] [2]
[1] [2, 3]
[1] [2] [3]

这不会像您的示例中那样生成空框，但是增加生成器来这样做是微不足道的。

有关迭代算法，请参阅 Michael Orlov（2002 年）的 "Efficient Generation of Set Partitions"。请注意，集合分区的数量增长非常很快，因此即使是迭代算法也需要一些时间来枚举即使是中等大小的集合的所有分区。

要计算设置分区的数量而不生成它们，请参阅Bell Numbers (OEIS A000110)。这是计算 Python:

中贝尔数的一种可能（不是很有效）的程序

def bell(n):
    "-> the n'th Bell number."
    assert n >= 0, n

    # loop will execute at least once
    for b in bell_sequence(n): 
        pass 

    return b

def bell_sequence(n):
    """Yields the Bell numbers b(0),b(1)...b(n).

    This function requires O(n) auxiliary storage.
    """
    assert n >= 0, n
    # compute Bell numbers using the triangle scheme
    yield 1 # b(0)

    row = [1] + (n-1)*[0]

    for i in range(0, n):
        row[i] = row[0]

        for k in reversed(range(i)):
            row[k] += row[k + 1]

        yield row[0] # b(i + 1)

排列 A 框中的 N 个元素？

Permutation o N elements in A boxes?

python

combinations

enumeration

permutation