algorithm to sum up a list of numbers for all combinations

Question

I have a list of numbers and I want to add up all the different combinations. For example:

• number as 1,4,7 and 13
• the output would be:

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

Is there a formula to calculate this with different numbers?

Answer 1

You can enumerate all subsets using a bitvector.

In a for loop, go from 0 to 2 to the Nth power minus 1 (or start with 1 if you don't care about the empty set).

On each iteration, determine which bits are set. The Nth bit represents the Nth element of the set. For each set bit, dereference the appropriate element of the set and add to an accumulated value.

ETA: Because the nature of this problem involves exponential complexity, there's a practical limit to size of the set you can enumerate on. If it turns out you don't need all subsets, you can look up "n choose k" for ways of enumerating subsets of k elements.

Answer 2

A simple way to do this is to create a bit set with as much bits as there are numbers. In your example 4.

Then count from 0001 to 1111 and sum each number that has a 1 on the set:

Numbers 1,4,7,13:

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

1111 = 1+4+7+13 = 25

Answer 3

The best-known algorithm requires exponential time. If there were a polynomial-time algorithm, then you would solve the subset sum problem, and thus the P=NP problem.

The algorithm here is to create bitvector of length that is equal to the cardinality of your set of numbers. Fix an enumeration (n_i) of your set of numbers. Then, enumerate over all possible values of the bitvector. For each enumeration (e_i) of the bitvector, compute the sum of e_i * n_i.

The intuition here is that you are representing the subsets of your set of numbers by a bitvector and generating all possible subsets of the set of numbers. When bit e_i is equal to one, n_i is in the subset, otherwise it is not.

The fourth volume of Knuth's TAOCP provides algorithms for generating all possible values of the bitvector.

Answer 4

This is not the code to generate the sums, but it generates the permutations. In your case:

1; 1,4; 1,7; 4,7; 1,4,7; ...

If I have a moment over the weekend, and if it's interesting, I can modify this to come up with the sums.

It's just a fun chunk of LINQ code from Igor Ostrovsky's blog titled "7 tricks to simplify your programs with LINQ" (http://igoro.com/archive/7-tricks-to-simplify-your-programs-with-linq/).

T[] arr = …;
var subsets = from m in Enumerable.Range(0, 1 << arr.Length)
              select
                  from i in Enumerable.Range(0, arr.Length)
                  where (m & (1 << i)) != 0
                  select arr[i];

Answer 5

that would be great if you could.

Answer 6

This Perl program seems to do what you want. It goes through the different ways to choose n items from k items. It's easy to calculate how many combinations there are, but getting the sums of each combination means you have to add them eventually. I had a similar question on Perlmonks when I was asking How can I calculate the right combination of postage stamps?.

The Math::Combinatorics module can also handle many other cases. Even if you don't want to use it, the documentation has a lot of pointers to other information about the problem. Other people might be able to suggest the appropriate library for the language you'd like to you.

#!/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 "combinations of $count from: [" . join(" ",@n) . "]\n";

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

Answer 7

C#:

I was trying to find something more elegant - but this should do the trick for now...

//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()
    );
}

Outputs as:

[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

Answer 8

Here's how a simple recursive solution would look like, in 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);
}

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 9

Here is a simple recursive Ruby implementation:

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)

Which prints

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

If you do not need to print the array at each step, the code can be made even simpler and much faster because no additional arrays are created:

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)

I dont think you can have it much simpler than that.

Answer 10

You might be interested in checking out the GNU Scientific Library if you want to avoid maintenance costs. The actual process of summing longer sequences will become very expensive (more-so than generating a single permutation on a step basis), most architectures have SIMD/vector instructions that can provide rather impressive speed-up (I would provide examples of such implementations but I cannot post URLs yet).

Answer 11

Hi 1,4,7 and 13 whats the logic of this sequence , i need a sequence where sum of any combination is unique?