在Python中设置最大大小为n的有序分区 [英] Set ordered partitions in Python of maximum size n

问题描述

我遇到的问题与以下相似，但不完全相同：
在Python中设置分区

I have a problem which is similar to the following but not quite exactly the same: Set partitions in Python

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

So I would like to achieve the same result as this other question, but I would like to block the maximum number of partitions to n, and only get ordered partitions. Also, the values in the partitions should be unique. As an example, the example from the question yielded the following partition for 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]]

就我而言，我只想获得以下内容：

As in my case, I would like to only obtain the following:

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 的示例，则需要产生以下内容：

Furthermore, I would like to be able to block the number of partitions to a number n. If I take an example where n=2, the following would need to be yielded:

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

请记住，我将要处理的最终数组的大小将大于1,000，因此这就是为什么我希望该算法高效，但能够将其限制为 n 分区。

Please bear in mind that the ultimate array I will be working on will be of size greater than 1,000, and therefore is why I would like the algorithm to be efficient, but be able to block it to n partitions.

推荐答案

如注释，其中 n 个不同的元素和 k 块或切片，生成将 k-1 分隔符放在 n中的所有选择就足够了-1 可能的位置：

As mentioned in the comments, with n distinct elements and k blocks or slices, it is sufficient to generate all choices of putting k-1 separators in n-1 possible positions:

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))

这将产生精确地<$ c $的除法c> k 个零件，对其进行修改以生成最多 k 个零件很简单。它还清楚地表明，结果中确实确实有 k C（n-1，k-1）元素c>零件。现在， C（1000，8）是 24,115,080,524,699,431,125 。完全可以尝试其他方法更好吗？

This generates divisions into exactly k parts, and it is trivial to modify it to generate up to k parts. It also makes it clear that there are indeed C(n-1, k-1) elements in the result for exactly k parts. Now, C(1000, 8) is 24,115,080,524,699,431,125. Probably better to try a different approach altogether?

这篇关于在Python中设置最大大小为n的有序分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！