在 Python 中设置最大大小为 n 的有序分区

Question

我遇到了一个与以下类似但又不完全相同的问题： Set partitions in Python

所以我想得到与这个问题相同的结果，但我想将最大分区数限制为n，并且只获取有序分区。此外，分区中的值应该是唯一的。例如，问题中的示例为 range(1,5)

生成了以下分区

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 3, 4], [2]]
5 [[1], [2], [3, 4]]
6 [[1, 2, 3], [4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
10 [[1, 2, 4], [3]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]

以我为例，我只想获取以下内容：

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1], [2], [3, 4]]
5 [[1, 2, 3], [4]]
6 [[1], [2, 3], [4]]
7 [[1, 2], [3], [4]]
8 [[1], [2], [3], [4]]

另外，我希望能够分块到一个数n。如果我以 n=2 为例，则需要生成以下内容：

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

请记住，我将要处理的最终数组的大小将大于 1,000，因此我希望算法高效，但能够将其阻塞到 n 分区。

Answer 1

如中所述，具有n个不同的元素和k个块或切片，足以生成将k-1个分隔符放在[中的所有选择=14=] 可能的职位：

from itertools import combinations

def segmentations(a, k):
    n = len(a)
    assert 1 <= k <= n, (n, k)

    def split_at(js):
        i = 0

        for j in js:
            yield a[i:j]
            i = j

        yield a[i:]

    for separations in combinations(range(1, n), k - 1):
        yield list(split_at(separations))

这会生成恰好 k 个部分，修改它以生成最多 k 个部分是微不足道的。它还清楚地表明结果中确实有 C(n-1, k-1) 个元素恰好 k 个部分。现在，C(1000, 8) 是 24,115,080,524,699,431,125。尝试完全不同的方法可能更好？

在 Python 中设置最大大小为 n 的有序分区

Set ordered partitions in Python of maximum size n

python

arrays

combinatorics