枚举具有N个元素的1d数组的所有k分区？
这似乎是一个简单的请求，但谷歌不是我的朋友，因为“分区”在数据库和文件系统空间中得分很多。
我需要将N个值（N是常数）的数组的所有分区枚举成k个子数组。 子数组就是 – 起始索引和结束索引。 将保留原始数组的整体顺序。
例如，N = 4且k = 2：
[ | abcd ] (0, 4) [ a | bcd ] (1, 3) [ ab | cd ] (2, 2) [ abc | d ] (3, 1) [ abcd | ] (4, 0) 并且k = 3：
[ | | abcd ] (0, 0, 4) [ | a | bcd ] (0, 1, 3) : [ a | b | cd ] (1, 1, 2) [ a | bc | d ] (1, 2, 1) : [ abcd | | ] (4, 0, 0)
我很确定这不是一个原始问题（不，它不是家庭作业），但我想为每个k <= N做这个，如果后来通过它会很好（因为k增长）利用了早期的结果。
如果您有链接，请分享。
为了重用先前的结果（对于较小的k值），可以进行递归。
将此类分区视为结束索引列表（任何分区的起始索引只是最后一个分区的结束索引，或者是第一个分区的结束索引）。
因此，您的分区集只是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矢量添加到结果列表中。
-
请注意，我的答案会生成每个切片的终点列表。 如果您（如您的示例所示）想要每个切片的LENGTHS列表，则需要通过从当前切片结尾减去最后切片结束来获取长度。
每个分区可以通过分隔各部分的k-1索引来描述。 由于保留了订单，因此这些指数必须不减少。 也就是说，大小为k-1的子集与您寻找的分区之间存在直接对应关系。
为了迭代大小为k-1的所有子集，您可以查看问题：
如何从java中的一组大小n迭代生成k个元素子集？
唯一的缺点是如果允许空白部分，几个切点可以重合，但是一个子集最多可以包含每个索引一次。 你必须通过替换来稍微调整算法：
processLargerSubsets(set, subset, subsetSize + 1, j + 1);
通过
processLargerSubsets(set, subset, subsetSize + 1, j);