陷入组合问题

Question

我的程序有问题。我提取了一组数据，我想测试是否存在特定数字的组合。例如，我有一个 int 数组，1 2 3 4 5，我想知道是否有 7 的组合，它必须回答是，有 3 + 4。

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

我不太擅长数学，定义的循环结构确实会有帮助。

预先非常感谢！

Answer 1

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

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、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 的任何内容

Answer 2

对于这个问题有一个简单的伪多项式时间动态规划，首先确定是否可以丰富 1 然后对于 sum 2 我们有两个选择，使用数组项之一，或者使用先前创建的1与新元素相加，您可以完成这个二维表直至丰富所要求的数字：

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)就足够了。

Answer 3

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

//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 的组合，您可以检查所有值并获取等于 6 的值的 x 和 y 索引。（在示例中：0/2、1/1 和 2/ 0）。然后在原始数组中查找这些索引处的数字（例如0/2 -> 1 和5、1/1 -> 3 和3、2/0 -> 5 和1）。

请注意，这是一种快速且性能不佳的方法（尤其是对于较大的数组），并且可能返回比您想要或需要的更多的排列（0/2 和 2/0 对于操作 add 是相同的）。然而，这应该适用于许多可能的操作，例如 x^y 对于 x=1, y=5（结果：1）和 x=5, y=1（结果：5）会有所不同。