枚举具有N个元素的1d数组的所有k分区？

Question

这似乎是一个简单的请求,但谷歌不是我的朋友,因为"分区"在数据库和文件系统空间中得分很多.

我需要将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),您可以进行递归.

将此类分区视为结束索引列表(任何分区的起始索引只是最后一个分区的结束索引,或者是第一个分区的结束索引).

因此,您的分区集只是k0到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列表,则需要通过从当前切片结尾减去最后一个切片结束来获取长度.