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

java combinations combinatorics

57603 просмотра

3 ответа

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

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

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");
        }
    }
}
Автор: Esostack Источник Размещён: 12.11.2019 09:40

Ответы (3)


48 плюса

Решение

Это хорошо изученная проблема генерации всех 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;
}
Автор: Alex Salauyou Размещён: 28.04.2015 09:02

5 плюса

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

Цитировать из статьи:

Способ 1 (исправить элементы и повторить)

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

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

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

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

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

Автор: Roney Michael Размещён: 28.04.2015 05:31

2 плюса

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

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

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);
    }
}

Обновить:

Вот оптимизированная версия, которая значительно сокращает количество обращений к 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];
        }
    }
}
Автор: Raniz Размещён: 28.04.2015 05:11
Вопросы из категории :
32x32