算法总结所有组合的数字列表

Question

我有一个数字列表,我想加起来所有不同的组合.例如:

• 数字为1,4,7和13
• 输出将是:

1+4=5
1+7=8
1+13=14
4+7=11
4+13=17
7+13=20
1+4+7=12
1+4+13=18
1+7+13=21
4+7+13=24
1+4+7+13=25

是否有一个公式来计算不同的数字？

Answer 1

一种简单的方法是使用与数字一样多的位来创建位集.在你的例子中4.

然后从0001计数到1111并对集合上每个数字1的数字求和:

数字1,4,7,13:

0001 = 13=13
0010 = 7=7
0011 = 7+13 = 20

1111 = 1+4+7+13 = 25

Answer 2

在Java中,这是一个简单的递归解决方案的样子:

public static void main(String[] args)
{
    f(new int[] {1,4,7,13}, 0, 0, "{");
}

static void f(int[] numbers, int index, int sum, String output)
{
    if (index == numbers.length)
    {
        System.out.println(output + " } = " + sum);
        return;
    }

    // include numbers[index]
    f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);

    // exclude numbers[index]
    f(numbers, index + 1, sum, output);
}

输出:

{ 1 4 7 13 } = 25
{ 1 4 7 } = 12
{ 1 4 13 } = 18
{ 1 4 } = 5
{ 1 7 13 } = 21
{ 1 7 } = 8
{ 1 13 } = 14
{ 1 } = 1
{ 4 7 13 } = 24
{ 4 7 } = 11
{ 4 13 } = 17
{ 4 } = 4
{ 7 13 } = 20
{ 7 } = 7
{ 13 } = 13
{ } = 0

Answer 3

最着名的算法需要指数时间.如果存在多项式时间算法,那么您将解决子集和问题,从而解决P = NP问题.

这里的算法是创建长度等于你的数字基数的bitvector.修复一(n_i)组数字的枚举.然后,枚举位向量的所有可能值.对于位(e_i)向量的每个枚举,计算总和e_i * n_i.

这里的直觉是,您通过位向量表示数字集的子集,并生成该组数字的所有可能子集.当位e_i等于1时,n_i在子集中,否则不在.

Knuth的TAOCP的第四卷提供了用于生成位向量的所有可能值的算法.

Answer 4

您可以使用位向量枚举所有子集。

在 for 循环中，从 0 到 2 的 N 次方负 1（如果不关心空集，则从 1 开始）。

在每次迭代中，确定设置了哪些位。第 N 位表示集合中的第 N 个元素。对于每个设置位，取消引用该组的适当元素并添加到累加值。

ETA：因为这个问题的本质涉及指数复杂性，所以您可以枚举的集合的大小存在实际限制。如果事实证明您不需要所有子集，则可以查找“n select k”以获取枚举 k 元素子集的方法。