枚举长度为N的一维数组的所有k分区？

Question

这似乎是一个简单的需求，但是谷歌并不是我的好朋友，因为“partition”在数据库和文件系统空间中得分很高。

我需要枚举一个包含N个值（N是常数）的数组的所有分区，将其分成k个子数组。子数组只是起始索引和结束索引。原始数组的整体顺序将被保留。

例如，当N=4且k=2时：

[ | a b c d ] (0, 4)
[ a | b c d ] (1, 3)
[ a b | c d ] (2, 2)
[ a b c | d ] (3, 1)
[ a b c d | ] (4, 0)

当k=3时：

[ | | a b c d ] (0, 0, 4)
[ | a | b c d ] (0, 1, 3)
  :
[ a | b | c d ] (1, 1, 2)
[ a | b c | d ] (1, 2, 1)
  :
[ a b c d | | ] (4, 0, 0)

我相信这不是一个原创问题（不，这不是作业），但我想为每个k <= N解决它，如果后续的计算（随着k的增长）能够利用之前的结果，那就太好了。

如果您有相关链接，请分享。

- Austin Hastings

---

你好，以下是翻译内容：使用k = 2看起来很简单；您能否提供一个更高的k的示例，最好是n值更高，以便问题更加清晰？ - Amarghosh

你的例子中(0,4)和(4,0)有相同的分区，即abcd，这是有意为之吗？ - Andrew White

安德鲁，这些分区是不同的。一个是|abcd，另一个是abcd|（空位在相反的两端）。 - Austin Hastings

Answer 1

为了重复利用之前的结果（对于较小的k值），您可以进行递归。

将这样的分区视为一系列结束索引（任何分区的起始索引只是上一个分区的结束索引，或者对于第一个分区为0）。

因此，您的分区集只是所有介于0和N之间的k个非递减整数数组的集合。

如果k受到限制，您可以通过k个嵌套循环来实现此目的。

for (i[0]=0; i[0] < N; i[0]++) {
    for (i[1]=i[0]; i[1] < N; i[1]++) {
    ...
            for (i[10]=i[9]; i[10] < N; i[10]++) {
                push i[0]==>i[10] onto the list of partitionings.
            }
    ...
    }
}

如果k没有限制，您可以进行递归操作。

在索引S和E之间获得一组k个分区的方法如下：

- 在S和E之间循环“第一个分区的结尾”EFP。对于每个值： - 递归地在EFP和S之间找到k-1个分区的列表。 - 对于该列表中的每个向量，在该向量之前添加“EFP”。 - 长度为k的结果向量添加到结果列表中。

请注意，我的答案生成每个切片端点的列表。如果您（如您的示例所示）需要每个切片的长度列表，则需要通过从当前切片结尾减去最后一个切片结尾来获得长度。

- DVK

Answer 2

每个分区都可以用k-1个索引来描述其部分。由于顺序被保留，这些索引必须是非递减的。也就是说，大小为k-1的子集与您寻找的分区之间有直接的对应关系。

要迭代所有大小为k-1的子集，您可以参考以下问题:

如何在Java中从大小为n的集合中迭代生成k元素子集？

唯一的问题是，如果允许空分区，则几个切点可能会重叠，但子集最多只能包含每个索引一次。您需要通过替换以下内容稍微调整算法：

        processLargerSubsets(set, subset, subsetSize + 1, j + 1);

由

        processLargerSubsets(set, subset, subsetSize + 1, j);

- meriton