Алгоритм для получения всех комбинаций размера n из массива (Java)?

В настоящее время я пытаюсь написать функцию, которая принимает массив и целое число n, и дает список каждой комбинации n размера (так что список массивов int). Я могу написать его, используя n вложенных циклов, но это работает только для определенного размера подмножества. Я не могу понять, как обобщить его для работы с любым размером комбинации. Я думаю, мне нужно использовать рекурсию?

Это код для всех комбинаций из трех элементов, и мне нужен алгоритм для любого количества элементов.

import java.util.List;
import java.util.ArrayList;

public class combinatorics{
    public static void main(String[] args) {

        List<int[]> list = new ArrayList<int[]>();
        int[] arr = {1,2,3,4,5};
        combinations3(arr,list);
        listToString(list);
    }

    static void combinations3(int[] arr, List<int[]> list){
        for(int i = 0; i<arr.length-2; i++)
            for(int j = i+1; j<arr.length-1; j++)
                for(int k = j+1; k<arr.length; k++)
                    list.add(new int[]{arr[i],arr[j],arr[k]});
    }

    private static void listToString(List<int[]> list){
        for(int i = 0; i<list.size(); i++){ //iterate through list
            for(int j : list.get(i)){ //iterate through array
                System.out.printf("%d ",j);
            }
        System.out.print("\n");
        }
    }
}

Ответ 1

Это хорошо изученная проблема генерации всех k-подмножеств или k-комбинаций, что легко можно сделать без рекурсии.

Идея состоит в том, чтобы массив размера k сохранял последовательность индексов элементов из входного массива (которые являются числами от 0 до n - 1) в порядке возрастания. (Затем подмножество может быть создано путем взятия элементов по этим индексам из исходного массива.) Таким образом, нам нужно сгенерировать все такие индексные последовательности.

Первая последовательность индексов будет [0, 1, 2, ... , k - 1], на втором шаге она переключится на [0, 1, 2,..., k], затем на [0, 1, 2, ... k + 1] и так далее. Последняя возможная последовательность будет [n - k, n - k + 1, ..., n - 1].

На каждом шаге алгоритм ищет ближайший к конечному элементу, который может быть увеличен, увеличивает его и заполняет элементы прямо к этому элементу.

Чтобы проиллюстрировать, рассмотрим n = 7 и k = 3. Первая индексная последовательность [0, 1, 2], затем [0, 1, 3] и т.д. В какой-то момент мы имеем [0, 5, 6]:

[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be
[1, ?, ?] <-- "0" -> "1"
[1, 2, 3] <-- fill up remaining elements

next iteration:

[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"

Таким образом, за [0, 5, 6] следует [1, 2, 3], затем идет [1, 2, 4] и т.д.

код:

int[] input = {10, 20, 30, 40, 50};    // input array
int k = 3;                             // sequence length   

List<int[]> subsets = new ArrayList<>();

int[] s = new int[k];                  // here we'll keep indices 
                                       // pointing to elements in input array

if (k <= input.length) {
    // first index sequence: 0, 1, 2, ...
    for (int i = 0; (s[i] = i) < k - 1; i++);  
    subsets.add(getSubset(input, s));
    for(;;) {
        int i;
        // find position of item that can be incremented
        for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--); 
        if (i < 0) {
            break;
        }
        s[i]++;                    // increment this item
        for (++i; i < k; i++) {    // fill up remaining items
            s[i] = s[i - 1] + 1; 
        }
        subsets.add(getSubset(input, s));
    }
}

// generate actual subset by index sequence
int[] getSubset(int[] input, int[] subset) {
    int[] result = new int[subset.length]; 
    for (int i = 0; i < subset.length; i++) 
        result[i] = input[subset[i]];
    return result;
}

Ответ 2

Если я правильно понял вашу проблему, эта статья указывает на то, что вы пытаетесь сделать.

Цитата из статьи:

Метод 1 (Fix Elements и Recur)

Мы создаем временные массивы 'data [], которые сохраняют все выходы один за один. Идея состоит в том, чтобы начать с первого индекса (индекс = 0) в данных [], один одним фиксирующим элементом по этому индексу и повторяется для оставшихся индексов. Позволять входной массив будет {1, 2, 3, 4, 5} и r равен 3. Сначала мы исправим 1 при индексе 0 в данных [], затем повторяется для оставшихся индексов, тогда мы фиксируем 2 в индексе 0 и повторять. Наконец, мы фиксируем 3 и повторяем для остальных индексов. когда количество элементов в данных [] становится равным r (размер комбинация), мы печатаем данные [].

Метод 2 (включить и исключить каждый элемент)

Подобно описанному выше методу, мы создаем временные данные массива []. Идея здесь похоже на проблему подмножества сумм. Мы один за другим рассматриваем каждый элемент входного массива и повторяется для двух случаев:

Элемент включен в текущую комбинацию (мы помещаем элемент в данные [] и увеличиваем следующий доступный индекс в данных [])

Элемент исключается в текущей комбинации (мы не помещаем элемент и не меняем индекс)
Когда количество элементов в данных [] становится равным r (размер сочетание), мы печатаем его.

Ответ 3

Вы можете сделать это с итерацией.

Здесь одно решение, которое вычисляет количество массивов, которые мы должны создать, а затем строит их с помощью математики, чтобы вычислить, какой элемент из исходного массива должен находиться в каком месте:

public static void combinations(int n, int[] arr, List<int[]> list) {
    // Calculate the number of arrays we should create
    int numArrays = (int)Math.pow(arr.length, n);
    // Create each array
    for(int i = 0; i < numArrays; i++) {
        int[] current = new int[n];
        // Calculate the correct item for each position in the array
        for(int j = 0; j < n; j++) {
            // This is the period with which this position changes, i.e.
            // a period of 5 means the value changes every 5th array
            int period = (int) Math.pow(arr.length, n - j - 1);
            // Get the correct item and set it
            int index = i / period % arr.length;
            current[j] = arr[index];
        }
        list.add(current);
    }
}

Update:

Здесь оптимизированная версия, которая значительно уменьшает количество вызовов Math.pow

public static void combinations(int n, int[] arr, List<int[]> list) {
    // Calculate the number of arrays we should create
    int numArrays = (int)Math.pow(arr.length, n);
    // Create each array
    for(int i = 0; i < numArrays; i++) {
        list.add(new int[n]);
    }
    // Fill up the arrays
    for(int j = 0; j < n; j++) {
        // This is the period with which this position changes, i.e.
        // a period of 5 means the value changes every 5th array
        int period = (int) Math.pow(arr.length, n - j - 1);
        for(int i = 0; i < numArrays; i++) {
            int[] current = list.get(i);
            // Get the correct item and set it
            int index = i / period % arr.length;
            current[j] = arr[index];
        }
    }
}