從n個組中查找所有組合的大小n

Question

我遇到編程問題 給定n組人員。 從每個組中挑選一個人組成一個新組。 如何從一組中找到所有可能的組合。

例如：如果我有2組 第1組：人A，B 第2組：人XYZ

可能集合將是（A，X）（A，Y）（A，Z）（ B，X）（B，Y）（B，Z）

謝謝任何​​幫助和建議。

推薦推薦。

Answer 1

您正在尋找n組的"product"。您可以遞歸實現這一點：

• 爲第一組
  • 中的每個元素的剩餘組的每個產品
    • 元素與產品相結合，並將其添加到結果

Python中的示例實現：

def product(lists, pos=0): 
    if pos < len(lists): 
     for x in lists[pos]: 
      for p in product(lists, pos+1): 
       yield [x] + p 
    else: 
     yield [] 

>>> list(product([[1,2,3], [4,5], [6,7,8]])) 
[[1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 5, 6], [1, 5, 7], [1, 5, 8], 
[2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 5, 6], [2, 5, 7], [2, 5, 8], 
[3, 4, 6], [3, 4, 7], [3, 4, 8], [3, 5, 6], [3, 5, 7], [3, 5, 8]] 

Answer 2

因爲在問題中沒有給出語言約束，所以我在java中共享代碼。代碼也計算兩組的叉積。

import java.util.*; 
import java.lang.*; 
import java.io.*; 


class Combinations 
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
     // your code goes here 
     System.out.println(prod(Arrays.asList(Arrays.asList("A", "B"), Arrays.asList("X", "Y", "Z")))); 
    } 

    static <String> List<List<String>> prod(List<List<String>> sets) { 
    List<List<String>> res = new ArrayList<List<String>>(); 
    if (sets.size() == 0) { 
     res.add(new ArrayList<String>()); 
     return res; 
    } else { 
     List<String> set1 = sets.get(0); 
     List<List<String>> adLst = prod(sets.subList(1, sets.size())); 
     for (String item : set1) { 
      for (List<String> lst : adLst) { 
       ArrayList<String> result = new ArrayList<String>(); 
       result.add(item); 
       result.addAll(lst); 
       res.add(result); 
      } 
     } 
    } 
    return res; 
} 
} 

輸出

[[A, X], [A, Y], [A, Z], [B, X], [B, Y], [B, Z]]