从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]]