与组合卡住问题

我遇到了问题w /我的程序。我提取了一组数据，我想测试一个特定数字是否有组合。例如，我有一个int数组，1 2 3 4 5，我想知道是否有7组合可能，并且它必须回答yes有3 + 4.与组合卡住问题

我发现我需要使用组合公式。所以我认为外层循环可能像5C1..5C2..5C3..etc一样，开始“取1”，然后“取2”，以找出所有可能的组合。问题是我坚持如何在实际代码中实现这一点。

我对数学并不是很好，定义好的循环结构真的有帮助。

非常感谢！

2011-03-15 maru

下面是获取所有可能的和从整数列表的方法：

public static void getAllPermutations(final List<Integer> data, 
    final Set<Integer> holder){ 

    if(data.isEmpty()){ 
     return; 
    } 
    final Integer first = data.get(0); 
    if(data.size() > 1){ 
     getAllPermutations(data.subList(1, data.size()), holder); 
     for(final Integer item : new ArrayList<Integer>(holder)){ 
      holder.add(first.intValue() + item.intValue()); 
     } 
    } 
    holder.add(first); 
}

用法：

List<Integer> data = Arrays.asList(1, 2, 3, 4, 5, 6); 
Set<Integer> permutations = new TreeSet<Integer>(); 
getAllPermutations(data, permutations); 
System.out.println(permutations);

输出：

[1,2 2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21 ]

尽管该方案不会给你带来的总和操作数，它将包括从1到1 + 2 + 3 + 4 + 5 + 6

来源

2011-03-15 10:27:04

正是我所需要的，非常感谢！ – maru 2011-03-15 11:09:32

一个快速和肮脏的解决方案可能是创建一个二维数组，其索引（在两个维度中）是数组在数组中的位置，数值是组合。事情是这样的：

//int i[] = { 1, 3, 5}, operation is 'add' 
//you have a 3x3 array here: 
//\ |1 3 5 <- the original values at their corresponding indices for quick reference, the array is the bottom right 3x3 matrix 
//--+------ 
//1 |2 4 6  
//3 |4 6 8 
//5 |6 8 10 

int[][] a = new int[3][3]; 
//in a loop fill the array

如果你现在要查找的组合为6，你可以检查所有值，并得到x和y指数是等于6的值（在这个例子中：0/2 ，1/1和2/0）。然后查找原始数组中那些索引处的数字（例如0/2 - > 1和5,1/1-> 3和3，2/0 - > 5和1）。

请注意，这是一种快速且非常不充分的方式（特别是对于较大的阵列），并且可能返回比您想要或需要的更多排列（对于操作add，0/2和2/0是相同的）。但是，这应该适用于许多可能的操作，例如对于x = 1，y = 5（结果：1）和x = 5，y = 1（结果：5），x ^y将是不同的。

来源

2011-03-15 10:24:24 Thomas

这是一个非常有创意的解决方案，tnx！ – maru 2011-03-15 11:07:35

什么有一个简单的伪多项式时间的动态规划这个问题，首先确定是可能的富裕1然后为2总和2我们有两个选项，使用一个数组项目，或者使用以前创建的1加上新元素，就可以完成这个2维表格到富要求的数字：

bool findNode(int[] C , int givenNumber) { 
// compute the total sum 
int n = C.Length; 
int N = 0; 
for(int i = 0; i < n; i++) N += C[i]; 
// initialize the table 
T[0] = true; 
for(int i = 1; i <= N; i++) T[i] = false; 
// process the numbers one by one 
for(int i = 0; i < n; i++) 
    for(int j = N - C[i]; j >= 0; j--) 
    if(T[j]) T[j + C[i]] = true; 

return T[givenNumber]; 
}

这是O（n * Sum）。实际上已经足够检查到O(n*given_number)。

来源

2011-03-15 10:49:41

与组合卡住问题

回答

相关问题