從數組（Java）中獲取大小爲n的所有組合的算法？

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的問題，它可以很容易地完成而無需遞歸。

的想法是具有遞增次序指數從輸入數組元素（其是從0到n - 1數）的大小保持k序列的陣列。 （子集然後可以通過從初始數組中獲取這些索引的項來創建）。因此我們需要生成所有這樣的索引序列。

第一個索引序列將是[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); 
    } 
} 

更新：

這是一個優化的版本，可以顯着減少撥打電話的次數到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（固定要素與岑參）

我們創建存儲所有輸出中的一個由一個 一個臨時數組「數據[]」。這個想法是從數據[]中的第一個索引（索引= 0）開始，一個 由該索引處的一個修復元素開始，而對於其餘索引則重複。設輸入數組爲{1,2,3,4,5}並且r爲3.我們首先在數據[]中的索引 0處固定1，然後對於其餘索引重複，然後我們在索引 0處固定2，並且復發。最後，我們修復3並重復其餘的索引。當 data []中的元素數等於r（ 組合的大小）時，我們打印數據[]。

方法2（包含和排除的每一個元素）

類似於上述方法，我們創建了一個臨時數組數據[]。這裏的想法 類似於子集總和問題。我們逐個考慮輸入陣列的每 元件，以及復發爲兩種情況：

1. 的元素被包括在當前的組合（我們把元件在數據[]和增量下一個可用的數據索引[]）
2. 元素被排除在當前組合（我們不把元件和不改變索引）

當在數據元素的數目[]變得等於r（一個 組合的大小），我們打印它。