算法：对于所有组合求和一个数字列表

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

有没有一种公式可以用不同的数字来计算这个问题？

- matt

---

这与欧拉计划有关吗？ - Kenan Banks

你要写一个Kakuro求解器（或创建器）吗？ - David Koelle

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

- Gamecat

---

很好的想法，但需要注意的是，如果你想要排除只有一个成员或没有成员的情况（就像你发布的问题中），你必须将它们排除在外（即二次幂和零），也就是说，如果你不想要没有成员的总和，就要把0000排除在外；如果你不想要只有一个成员的总和，就要把0001、0010、0100、1000排除在外。 - user334911

你能否解释一下或者给一个链接？ - sayem siam

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

- Zach Scrivena

Answer 3

最著名的算法需要指数时间。如果有一个多项式时间算法，则可以解决 子集和问题，从而解决 P=NP 问题。

这里的算法是创建长度等于您数字集合基数的位向量。固定一个枚举 (n_i) 您的数字集合。然后，枚举所有可能的位向量值。对于位向量的每个枚举 (e_i)，计算 e_i * n_i 的和。

这里的直觉是，通过位向量表示数字集合的子集，并生成数字集合的所有可能子集。当位 e_i 等于一时，n_i 在子集中，否则不在。

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

- Jason

---

他想要输出每一个总和。如果是这样，那么问题肯定是非多项式的，因为输出与输入成指数关系，因此不属于P=NP范畴。 - mweiss

Answer 4

C#:

我一直在尝试寻找更优雅的解决方案，但现在这个应该可以暂时解决问题了...

//Set up our array of integers
int[] items = { 1, 3, 5, 7 };

//Figure out how many bitmasks we need... 
//4 bits have a maximum value of 15, so we need 15 masks.
//Calculated as:
//    (2 ^ ItemCount) - 1
int len = items.Length;
int calcs = (int)Math.Pow(2, len) - 1;

//Create our array of bitmasks... each item in the array
//represents a unique combination from our items array
string[] masks = Enumerable.Range(1, calcs).Select(i => Convert.ToString(i, 2).PadLeft(len, '0')).ToArray();

//Spit out the corresponding calculation for each bitmask
foreach (string m in masks)
{
    //Get the items from our array that correspond to 
    //the on bits in our mask
    int[] incl = items.Where((c, i) => m[i] == '1').ToArray();

    //Write out our mask, calculation and resulting sum
    Console.WriteLine(
        "[{0}] {1}={2}", 
        m, 
        String.Join("+", incl.Select(c => c.ToString()).ToArray()), 
        incl.Sum()
    );
}

输出为：

[0001] 7=7
[0010] 5=5
[0011] 5+7=12
[0100] 3=3
[0101] 3+7=10
[0110] 3+5=8
[0111] 3+5+7=15
[1000] 1=1
[1001] 1+7=8
[1010] 1+5=6
[1011] 1+5+7=13
[1100] 1+3=4
[1101] 1+3+7=11
[1110] 1+3+5=9
[1111] 1+3+5+7=16

- balabaster

Answer 5

这里是一个简单的递归Ruby实现：

a = [1, 4, 7, 13]

def add(current, ary, idx, sum)
    (idx...ary.length).each do |i|
        add(current + [ary[i]], ary, i+1, sum + ary[i])
    end
    puts "#{current.join('+')} = #{sum}" if current.size > 1
end    
add([], a, 0, 0)

打印哪些内容

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
4+7+13 = 24
4+7 = 11
4+13 = 17
7+13 = 20

如果您不需要在每个步骤打印数组，则可以使代码更简单且速度更快，因为不会创建额外的数组：

def add(ary, idx, sum)
    (idx...ary.length).each do |i|
        add(ary, i+1, sum + ary[i])
    end
    puts sum
end
add(a, 0, 0)

我认为你不可能比这更简单了。

- martinus

Answer 6

这个Perl程序似乎可以实现你想要的功能。它会遍历选择n项中的k项的不同方式。虽然容易计算出有多少种组合，但获取每个组合的总和意味着最终必须将它们相加。当我询问如何计算正确的邮票组合？时，在Perlmonks上也有类似的问题。 Math::Combinatorics模块还可以处理许多其他情况。即使您不想使用它，文档也提供了许多指向有关该问题的其他信息的指针。其他人可能能够为您建议适用于所需语言的适当库。

#!/usr/bin/perl use List::Util qw(sum); use Math::Combinatorics;

my @n = qw(1 4 7 13);

foreach my $count ( 2 .. @n ) { my $c = Math::Combinatorics->new( count => $count, # number to choose data => [@n], );

print "从 [" . join(" ",@n) . "] 中选择 $count 个数的组合：\n";

while( my @combo = $c->next_combination ){ print join( ' ', @combo ), " 的和为 ", sum( @combo ) , "\n"; } }

- brian d foy

Answer 7

Mathematica解决方案:

{#, Total@#}& /@ 子集[{1, 4, 7, 13}]  //矩阵格式化

输出结果:

{}  0
{1} 1
{4} 4
{7} 7
{13}    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

- dreeves

Answer 8

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

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

在每次迭代中，确定哪些位被设置。第N位表示集合的第N个元素。对于每个集合位，请取消引用相应的集合元素并添加到累积值中。

预计时间：由于这个问题的本质涉及指数复杂度，因此您可以枚举的集合大小有实际限制。如果发现您不需要所有子集，则可以查找“n choose k”以枚举k个元素的子集的方法。

- JasonTrue

---

指的是指数复杂度，而不是多项式复杂度。 - recursive

2^N增长非常快，很快就会超过大多数编程语言中可以表示的标准数据类型中最大整数的大小。因此，对于较大的N，必须使用另一种算法来生成所有位向量。 - jason

Rec：抱歉，是的，已经更正了。虽然它是二项式... Jason：BitVector可以是任意长度，但如何实现任意长度可能取决于您的语言。如果位向量的接口足够抽象，则子集算法不需要针对更大的位向量进行更改。 - JasonTrue

如果我误读了您的帖子，我很抱歉，但您提到使用从0到2^N-1的for循环来生成比特向量。我想说的是，对于非常大的N，2^N将超过大多数编程语言中最大整数数据类型（例如C#中的Int64）的大小。 - jason

是的，但是BitVector并不与实现绑定。算法是相同的。在大多数（非Lispish）语言中，您可能需要使用LargeNumber类。对于2^64，您有太多的子集需要枚举，这在实践中是不可行的。 - JasonTrue

我应该说，您可能需要使用LargeNumber来表示索引值。但是，仅适用于大于64个元素的集合，这些集合通常太大而无法枚举所有子集。 - JasonTrue

Answer 9

PHP：这里是一个非递归实现。我并不是说这是最有效的方法（事实上，这确实是指数级的2^N——请参见JasonTrue的回答和评论），但它适用于一小组元素。我只是想快速写点什么来获得结果。我基于Toon的答案编写了算法。

$set = array(3, 5, 8, 13, 19);

$additions = array();
for($i = 0; $i < pow(2, count($set)); $i++){
    $sum = 0;
    $addends = array();
    for($j = count($set)-1; $j >= 0; $j--) {
        if(pow(2, $j) & $i) {
            $sum += $set[$j];
            $addends[] = $set[$j];
        }
    }
    $additions[] = array($sum, $addends);
}

sort($additions);

foreach($additions as $addition){
    printf("%d\t%s\n", $addition[0], implode('+', $addition[1]));
}

将输出：

0   
3   3
5   5
8   8
8   5+3
11  8+3
13  13
13  8+5
16  13+3
16  8+5+3
18  13+5
19  19
21  13+8
21  13+5+3
22  19+3
24  19+5
24  13+8+3
26  13+8+5
27  19+8
27  19+5+3
29  13+8+5+3
30  19+8+3
32  19+13
32  19+8+5
35  19+13+3
35  19+8+5+3
37  19+13+5
40  19+13+8
40  19+13+5+3
43  19+13+8+3
45  19+13+8+5
48  19+13+8+5+3

例如，一个这样的案例可能是一组用于锻炼的阻力带。假设你获得了5根带子，每个带子都代表着不同的抗力，以磅为单位，你可以将带子结合起来以得到总阻力。这些带子的抗力分别为3、5、8、13和19磅。这个集合给你提供了32种（2^5）可能的组合方式，除了零。在这个例子中，算法按照总阻力升序排列数据，优先考虑效率高的带子组合，而对于每种组合，带子按照抗力降序排列。

- djule5

Answer 10

v=[1,2,3,4]#variables to sum
i=0
clis=[]#check list for solution excluding the variables itself
def iterate(lis,a,b):
    global i
    global clis
    while len(b)!=0 and i<len(lis):
        a=lis[i]
        b=lis[i+1:]
        if len(b)>1:
            t=a+sum(b)
            clis.append(t)
        for j in b:
            clis.append(a+j)
        i+=1
        iterate(lis,a,b)
iterate(v,0,v)

这是用Python编写的程序。其思路是将列表分解为一个整数和一个列表，例如[1,2,3,4]变成1,[2,3,4]。我们通过添加整数和剩余列表的总和来附加总和，同时我们还要取每个单独的总和，即1,2;1,3;1,4。检查表现在应该是[1+2+3+4,1+2,1+3,1+4]，然后我们递归调用新列表，即现在int=2，list=[3,4]。相应地，检查表将附加[2+3+4,2+3,2+4]，直到列表为空为止。

- Niraj Verma

---

你能否请附上一些解释。谢谢。 - kinshuk4

这段代码的思路是将列表分为一个整数和一个列表，例如[1,2,3,4]变成了1,[2,3,4]。我们通过添加整数和剩余列表的总和来附加总和，同时我们还要取每个单独的总和，即1,2;1,3;1,4。现在检查清单应该是[1+2+3+4,1+2,1+3,1+4]，然后我们递归调用新列表，即现在int=2，list=[3,4]。检查清单现在将附加[2+3+4,2+3,2+4]，相应地，我们附加检查清单，直到列表为空。如果您想，我可以向您发送此过程的图表。 - Niraj Verma

嗨Niraj， 请在你的答案中更新这个评论。这将有助于未来的用户。 - kinshuk4