寻找将数组拆分为 k 数组的有效方法

Question

我正在尝试创建一个程序，该程序采用递增顺序的整数数组并将其拆分为 k 个递增顺序的非空数组，当将其合并为一个数组时会产生原始数组 - 第一个数组不能包含任何但第一个或多个数字（k1=[1,2,3] 有效但 k1=[2,3,4] 无效）

到目前为止，我已经尝试给定一个 array[4,7,11,21,31] 和 k=3 硬编码两个 for 循环，它们充当复制项目并将原始数组的一部分复制到受尊重的位置的指针变量

int[] array = {1,2,3,4,5};
     int k = 3;
     int n = 5; 
     for(int i = 0; i <= n - k; i++){
       for(int j = i+1; j < n-1; j++){
         int[] k1 = Arrays.copyOfRange(array , 0, i+1);
         int[] k2 = Arrays.copyOfRange(array , i+1, j+1);
         int[] k3 = Arrays.copyOfRange(array , j+1, n);
       }
     }

上面的代码适用于 k=3 但问题是我不知道如何有效地使其适用于任何 k 并有效地存储数组

最终目标是生成所有可能的组合

Answer 1

这种递归蛮力方法并没有真正拆分数字数组，它只是 return 数组条目的索引，其中必须进行拆分。

它有两个参数：

n数组的长度
k想要的零件数

它将 return 一个 ArrayList<int[]> 包含所有可能的拆分组合（每个组合都是一个索引数组，其中 k-1 个元素按升序排列）。

我已经尝试了一些案例，它似乎有效。正如预期的那样，它似乎总是 return 二项式系数 (n-1) over (k-1) 数量的组合。这是因为在任何长度为 n 的数组中，都有 n-1 处可以将其一分为二。不过，我们只想将其拆分 k-1 次（以 k 部分结束）。所以这基本上是从 n-1 中选择 k-1，因此是二项式系数。

public static ArrayList<int[]> getSplits(int n, int k) {
    if (k == 1) {
        return new ArrayList<int[]>();
    }

    ArrayList<int[]> newSplits = new ArrayList<int[]>();

    for (int s = 1; s < n-(k-1)+1; s++) {
        if (k == 2) {
            newSplits.add(new int[] {s});
        } else {
            ArrayList<int[]> splits = getSplits(n-s, k-1);

            for (int[] split : splits) {
                int[] newSplit = new int[split.length + 1];
                newSplit[0] = s;
                for (int i = 0; i < split.length; i++) {
                    newSplit[i+1] = split[i] + s;
                }
                newSplits.add(newSplit);
            }
        }
    }
    return newSplits;
}

在您问题的上下文中使用：

要从中获取数组部分，您可以使用此函数。它输出由管道符号分隔的它们 (|).

public static void main(String args[]) {
    int[] array = new int[] {1, 2, 3, 4};
    int n = array.length;
    int k = 3;

    ArrayList<int[]> splits = getSplits(n, k);

    for (int[] split : splits) {
        int j = 0;
        for (int i = 0; i < split.length; i++) {
            for (; j < split[i]; j++) {
                System.out.print(array[j] + " ");
            }
            System.out.print("| ");
        }
        for (; j < n; j++) {
            System.out.print(array[j] + " ");
        }
        System.out.println();
    }
}

这将打印以下内容（将 4 个项目拆分为 3 个非空组的所有可能性）：

1 | 2 | 3 4 
1 | 2 3 | 4 
1 2 | 3 | 4

寻找将数组拆分为 k 数组的有效方法

Looking for efficient way of splitting array into k-arrays

java

arrays

partitioning