从n个组中查找所有组合的大小n
我遇到编程问题 给定n组人员。 从每个组中挑选一个人组成一个新组。 如何从一组中找到所有可能的组合。从n个组中查找所有组合的大小n
例如:如果我有2组 第1组:人A,B 第2组:人XYZ
可能集合将是(A,X)(A,Y)(A,Z)( B,X)(B,Y)(B,Z)
谢谢任何帮助和建议。
推荐推荐。
您正在寻找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]]
你的代码很简单优雅,多谢 –
因为在问题中没有给出语言约束,所以我在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]]
'static'那么'String'是类型占位符的名字吗?非常容易混淆...... –
字符串(java中的数据类型)就是列表中所包含对象的类型。它可以更改为其他数据类型,如Integer –
不,它不是。在第一个'
这是不是一个编程的问题......而且,你找谁只是尺寸为2的组合? – alfasin
你知道如何用手解决这个问题吗?如果是这样,请尝试一下并编辑您的问题以包含特定问题。如果不是,请先从那里开始。 –