Блог

Главная - Вопросы по программированию - Ищете эффективный способ разделения массива на k-массивы

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

#java #arrays #partitioning

#java #массивы #разделение

Вопрос:

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

До сих пор я пытался использовать два цикла for с жестким кодированием array[4,7,11,21,31] и k=3 , которые действуют как указатели на то, куда копировать элементы, и копирование части исходного массива в соответствующие переменные

 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 и эффективно хранить массивы

Конечная цель — сгенерировать все возможные комбинации

Комментарии:

1. Итак, вы хотите иметь все возможные комбинации k непустых массивов, которые при объединении создают исходный массив?

2. @TheBlackIPs Да, это правильно. Например, k1 = [1,2] k2 = [3,4] k3= [5]. k1 не может содержать ни одной цифры, которая не является первой или первой и следующей. Также не обязательно, чтобы это были массивы. Это то, что я использовал для своей первоначальной попытки.

3. Если мы говорим об эффективности, будет ли достаточно просто иметь индексы, в которых находится каждый из разделений? ( i 1 и j 1 в этом примере)

4. @TheBlackIPs Ну, не совсем уверен. Я ищу эффективность меньше O (n * n * n * k), где n — размер исходного массива

5. Да, но какова задача под рукой? Каковы требования? Вы сказали, что это не обязательно должны быть массивы, каким может быть результат тогда?

Ответ №1:

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

Для этого требуется два аргумента:

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

Он вернет an 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