第N個組合（{a，b} = {b，a}）不重複（枚舉/蠻力）

Question

我正在尋找一種算法，可以生成沒有重複的第n個組合。

我可以找到很多關於排列(a, b) != (b, a)，但我正在尋找組合，其中{a, b} = {b, a}。

例子：

Set = {a, b, c} 
n = 2 
Combinations: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d} 

Java中的通用，遞歸實現，將一組或列表將是巨大的。我也希望鏈接有一個很好的解釋，僞代碼或示例代碼。

Answer 1

爲此，您可以使用下面的遞歸方法創建的列表：

public static<T> ArrayList<ArrayList<T>> getPermutations (List<T> elements, int k) { 
    return getPermutations (elements,k,0); 
} 

public static<T> ArrayList<ArrayList<T>> getPermutations (List<T> elements, int k, int i) { 
    ArrayList<ArrayList<T>> results = new ArrayList<>(); 
    if(k > 0) { 
     int n = elements.size(); 
     for(int j = i; j <= n-k; j++) { 
      T val = elements.get(j); 
      ArrayList<ArrayList<T>> tails = getPermutations(elements,k-1,j+1); 
      for(ArrayList<T> tail : tails) { 
       ArrayList<T> result = new ArrayList<>(); 
       result.add(val); 
       result.addAll(tail); 
       results.add(result); 
      } 
     } 
    } else { 
     results.add(new ArrayList<T>()); 
    } 
    return results; 
} 

你然後可以運行它（jDoodle）：

ArrayList<Character> set = new ArrayList<>(); 
set.add('a'); 
set.add('b'); 
set.add('c'); 

for(ArrayList<Character> element : getPermutations(set,2)) { 
    System.out.println(element); 
} 
System.out.println("----------"); 
for(ArrayList<Character> element : getPermutations(set,3)) { 
    System.out.println(element); 
} 
System.out.println("----------"); 

set.add('d'); 

for(ArrayList<Character> element : getPermutations(set,2)) { 
    System.out.println(element); 
} 
System.out.println("----------"); 
for(ArrayList<Character> element : getPermutations(set,3)) { 
    System.out.println(element); 
} 

產生：

[a, b] 
[a, c] 
[b, c] 
---------- 
[a, b, c] 
---------- 
[a, b] 
[a, c] 
[a, d] 
[b, c] 
[b, d] 
[c, d] 
---------- 
[a, b, c] 
[a, b, d] 
[a, c, d] 
[b, c, d] 

---

程序的工作原理如下：k是我們仍然要挑元素的數量，並且i是當前偏移值。最初該偏移值是0。

現在我們從i重複n-k尋找潛在的候選人成爲頭的一部分。該範圍內的每個元素將成爲某些組合的頭部。我們對列表的其餘部分執行遞歸。遞歸生成列表中剩餘部分的所有列表，其中包含k-1元素。那麼我們的工作就是在前面添加一個頭並返回列表。

通過使用特殊形式的LinkedList（這在邏輯和函數式編程語言中很常見），可以實現更快和更保守的內存保存。

Answer 2

遞歸算法是容易的：

1. 刪除第一個元素。
2. 與列表中
3. 相互元素配對加入該列表由其餘元素

Answer 3

你還記得找到k-th permutations of the elements的問題嗎？沒有多少人知道算法背後的原因，但它背後有數學理論。可以通過在factorial number system中表示數字來解決。

爲什麼我談論第k個排列如果問題是關於尋找第k個組合？只是因爲它可以用類似的數學理論來解決。驚奇，驚奇，有一個combinatorial number system：

集S的K組合是S的具有k（不同） 元素的子集。組合數字系統的主要目的是提供一個表示，其中每一個都由單個數字組成，其中n個元素的集合的可能的k個組合。

閱讀文章，很可能您將能夠解決您的問題。

Answer 4

給定的輸入list和n，分裂成list第一項和列表的其餘部分稱他們head和tail。然後，你所尋求的組合是：

• 你可以從tail和n讓你可以從tail和n-1得到的組合，再加上
• 組合，每個head前置

如果n爲0，結果只是一種組合：{}

如果n大於的大小，結果是沒有組合

---

邊注：爲了好玩，我在Haskell解決了這個，把n = 0的情況下，在頂部：

comb 0 _ = [[]] 
comb n (head:tail) | n > 0 = comb n tail ++ map (head:) (comb (n-1) tail) 
comb _ _ = []