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

Question

Прямо сейчас я пытаюсь написать функцию, которая принимает массив и целое число 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"); 
     } 
    } 
} 

Answer 1

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

Идея заключается в том, чтобы иметь массив размера 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; 
} 

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

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

Answer 3

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

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

Метод 1 (FIX элементы и повторялись)

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

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

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

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

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