java - 枚举具有 N 个元素的一维数组的所有 k 分区？

Question

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

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

如果您有链接，请分享。

Answer 1

为了重新使用先前的结果(对于较小的 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。对于每个值:

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

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

  • 长度为 k 的结果 vector 被添加到结果列表中。

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