7

这似乎是一个简单的请求，但 google 不是我的朋友，因为“分区”在数据库和文件系统空间中获得了很多点击。

我需要将 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 增长) 利用了早期的结果。

如果你有链接，请分享。

4

2 回答 2

7

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

将此类分区视为结束索引的列表（任何分区的起始索引只是最后一个分区的结束索引或第一个分区的结束索引为 0）。

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

如果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是无限的，你可以递归地做。

k索引 S 和 E 之间的一组分区通过以下方式获得：

  • 在 S 和 E 之间循环“第一个分区结束”EFP。对于每个值：

    • 递归查找k-1EFP 和 S 之间的分区列表

    • 对于该列表中的每个向量，在该向量前面加上“EFP”。

    • 结果向量的长度k被添加到结果列表中。

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

于 2010-12-30T15:25:19.043 回答
1

每个分区可以通过分隔各个部分的 k-1 个索引来描述。由于保留了顺序，因此这些索引必须是非递减的。也就是说，大小为 k-1 的子集与您寻找的分区之间存在直接对应关系。

要迭代所有大小为 k-1 的子集，您可以查看以下问题：

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

唯一的问题是，如果允许空部分，几个切点可以重合，但一个子集最多可以包含每个索引一次。您必须通过替换来稍微调整算法：

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

经过

        processLargerSubsets(set, subset, subsetSize + 1, j);
于 2010-12-30T15:27:54.077 回答