用於計算排列而不重複的Java函數

我有一個ArrayList，我希望找到一個給定大小的所有組合，而不用重複其內部的單個函數（內置或不內置）。例如：用於計算排列而不重複的Java函數

ArrayList<Integer> numbers = Array.asList(96, 32, 65, 21); 
getCombinationsWithoutRepeats(numbers, 2);

輸出：

>>> [[96, 32], [96, 65], [96, 21], [32, 65], [32, 21], [65, 21]]

我將如何創造這個功能還是有，這是否一個內置的功能？

來源

2013-06-23 LazySloth13

相關：[數組排列]（http://stackoverflow.com/a/2920349/335858）。 – dasblinkenlight

我們可以假設輸入數組只有唯一的元素（我假設你在輸出中指的是「重複」）？一個非常明顯的解決方案是首先生成大小爲'n'的所有組合（最常見的方法是用一個「n」位數表示該組，並且每次重複增加。每次，數字的按位表示都會告訴您哪些元素包含/排除在當前組合中），然後對每個組合進行排列（例如，流行的詞典解決方案：http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order）。 – rliu

你試過了什麼？ – Ayman

-1

這是一個使用回溯的示例解決方案。它會生成大小爲K的所有可能的排列，並將它們存儲在lists字段中。

List<List<Integer>> lists = new ArrayList<List<Integer>>(); 

void permutate(int[] arr, int k) { 
    internalPermutate(arr, k, 0, 0); 
} 

void internalPermutate(int[] arr, int k, int step, int index) { 
    if (step == k) { 
     List<Integer> list = new ArrayList<Integer>(); 
     for (int i = 0; i < k; i++) { 
      list.add(arr[i]); 
     } 
     lists.add(list); 
    } 

    for (int i = step + index; i < arr.length; i++) { 
     swap(arr, step, i); 
     internalPermutate(arr, k, step + 1, i); 
     swap(arr, step, i); 
    } 
} 

private void swap(int[] arr, int x, int y) { 
    int temp = arr[x]; 
    arr[x] = arr[y]; 
    arr[y] = temp; 
} 

public static void main(String[] args) { 
    new SomeClass().permutate(new int[] { 1, 2, 3, 4 }, 2); 
    System.out.println(lists); 
}

此解決方案不處理情況，當我們在數組中有相同的元素，但你可以在排列之前排除它們。

來源

2013-06-23 11:04:58 Desert

這對於k = 1以上的任何內容都不起作用 – CODe

用於計算排列而不重複的Java函數

回答

相關問題