Ищем эффективный способ разбиения массива на k-массивы

Question

Я пытаюсь создать программу, которая принимает целочисленный массив в возрастающем порядке и разбивает его на k непустых массивов в возрастающем порядке, которые при объединении в один массив создают исходный массив - первый массив не может содержать ни одного, кромепервая или более цифр (k1 = [1,2,3] допустимо, но k1 = [2,3,4] нет)

До сих пор я пытался дать array[4,7,11,21,31] и k=3 hard-кодирование двух циклов 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

Этот рекурсивный метод грубой силы на самом деле не разбивает массив чисел, он просто возвращает индексы записей массива, где должно произойти расщепление.

Требуется два аргумента:

• n длина массива
• k количество требуемых деталей

Он вернет ArrayList<int[]>, который содержит все возможные комбинации расщеплений (каждая из которых представляет собой массив индексов с k-1 элементами в порядке возрастания).

Я пробовал некоторые случаи, и похоже, что это работает,Как и ожидалось, он всегда возвращает биномиальный коэффициент (n-1) over (k-1) количество комбинаций.Это связано с тем, что в любом массиве длиной n есть n-1 мест, где его можно разделить на две части.Мы только хотим разделить это k-1 раз, хотя (в итоге k частей).Так что это в основном выбор k-1 из n-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