Arch Linux

br4

Member

Registered: 2007-12-27

Posts: 38

[Solved] How can i calculate all possible sums of an int array?

Hi,
i can't figure out the algorithm for that:
e.g. array=1,2,3,..n => P1=1+2,P2=1+3,P3=2+3,P4=1+2+3,...
For a program language i use Java.

thanks.

Last edited by br4 (2008-12-10 15:23:40)

string

Member

Registered: 2008-11-03

Posts: 286

Re: [Solved] How can i calculate all possible sums of an int array?

Idea:

Let V be the array and N the number of elements in V. Computing "sum_number_P":

-> Assume the binary representation of P is: bN b(N-1) ... b3 b2 b1 (where bJ = "bit number J", bN = MSB, b1 = LSB).
=> sum_number_P = bN * V[N - 1] + b(N-1) * V[N - 2] + ... + b1 * V[0]

Now compute sum_number_1, sum_number_2, .... sum_number_(2^N - 1)

--

An example: Let V = { 1, 2, 3 } ; N = 3.

sum_number_1:
-> 1 = 001 (in base 2)
=> sum_number_1 = 0 * V[2] + 0 * V[1] + 1 * V[0] = 0 * 3 + 0 * 2 + 1 * 1 = 1

sum_number_2:
-> 2 = 010 (in base 2)
=> sum_number_2 = 0 * V[2] + 1 * V[1] + 0 * V[0] = 0 * 3 + 1 * 2 + 0 * 1 = 2

sum_number_3:
-> 3 = 011 (in base 2)
=> sum_number_3 = 0 * V[2] + 1 * V[1] + 1 * V[0] = 0 * 3 + 1 * 2 + 1 * 1 = 3

...

sum_number_(2^3 - 1) = sum_number_7:
-> 7 = 111
=> sum_number_7 = 1 * V[2] + 1 * V[1] + 1 * V[0] = 1 * 3 + 1 * 2 + 1 * 1 = 6

Last edited by string (2008-12-08 16:46:47)

br4

Member

Registered: 2007-12-27

Posts: 38

Re: [Solved] How can i calculate all possible sums of an int array?

Thank you string.
that really helped me + i learned something new (Bit Numbers). And I think i will be able to transform it to Java-code.

catwell

Member

From: Bretagne, France

Registered: 2008-02-20

Posts: 207

Website

Re: [Solved] How can i calculate all possible sums of an int array?

Recursive algorithm in some kind of pseudocode:

f(array, sums):
  if array == [] then return sums
  else
    newsums = {array[1]}
    for i in sums do
      newsums.append(i)
      newsums.append(array[1]+i)
    done
    return f(array[2:], newsums)
  end

f(my_array, {})

The things I write in brackets are sets (implement them the way you want). The result is not exactly the one you wanted because it includes the elements of the original table (they're sums of only one element), do the necessary changes by yourself if you don't want that behavior.

string

Member

Registered: 2008-11-03

Posts: 286

Re: [Solved] How can i calculate all possible sums of an int array?

Good stuff.

Last edited by string (2008-12-09 08:26:30)

br4

Member

Registered: 2007-12-27

Posts: 38

Re: [Solved] How can i calculate all possible sums of an int array?

finally i had time to write it. Thanks for the ideas .

Last edited by br4 (2009-08-06 06:45:18)