# How to iterate between these elements

I have an array of elements:

``````int[] elem = new int[] {A, B, C};
``````

I need to calculate the sum of ALL the combinations of those elements, where only some of the elements can be optionally selected. I will use the notation:

• {0,1} mean element can be selected or not
• {1} mean element is always selected.

Therefore, I need to calculate the following value, which could be something like:

``````result = {0,1}*A + {1}*B + {0,1}*C;
``````

I have tried to use nested for loops, like so:

``````for (int i=0;i<2;i++)
for (int j=1;j<2;j++) // notice I start at 1, not 0, because B is {1}
for (int k=0;k<2;k++)
Console.Write( i*A + j*B + k*C );
``````

There are two problems with this:

• These nested for loops are rather cumbersome
• My example only has three elements, but the array could be of any size. For example, if the array had 10 elements, I would need to have 10 nested loops instead of three. I don't know to change the number of for loops based on the array size.

How would I iterate to get all sum values for all combinations in an arbitrary sized array?

• Using a 5 element example in the question only serves to make the question more complicated and harder to follow. A three element example serves the same purpose and can drive the same point across – durron597 May 22 '15 at 15:07

You are computing the sum of all the combinations of a set of numbers.

The number of combinations you have is 2n, where `n` is the number of numbers. For example, if your array had 5 elements, it would be 25 which is 32. The combinations that you will be iterating through are the binary representations of 0..31.

`00000`
`00001`
`00010`
`00011`
...
`11111`

This has the additional constraint that the value must be `.1...` which can be easily filtered with a bitmask:

`````` for i = 0 .. 2**elem.size - 1
next unless i & 0b01000
``````

After this, you walk the bits and sum up the values:

``````    sum = 0
mask = 0b00001  # written out, its just 1
for j = 0 .. elem.size
sum += elem[j] * ((i & mask) >> j)
print sum
``````

I'll admit to the possibility that there's a fencepost or off by one error in there, but this is fairly simple loops that may be even simpler (or harder) depending on the implementation language. Just a little bit of bit math.

The key part of this is walking over the bits of `i`. We start out with a max with only the lowest bit set (`0b00001` which is also just a plain old `1`). Then, for each element of the array, do a bitwise and of the mask and `i`. If the bit is set, this is a power of 2 (20, 21, 22 ...) that we then have to shift back the number of positions to make it either 1 (if the bit was set) or 0 (if the bit was not set). This is done with the `>>` operator. This could also be done by dividing by the appropriate power of 2.

Once we get 1 or 0 back from the bit math, multiply it by the element at the associated array index and then add that to the sum.

To move to the next position, the mask is shifted to the left one bit (so that `0b00001` becomes `0b00010`) which can also be done with a `*= 2` if you didn't want to work with bits.

• This looks like what I need. But my lenguaje of choice are C# or VB.net, can you explain a litle more about what mean `(i & mask >> j)`? my guess is return {0,1} but dont understand how. And then why `mask <<= 1` . – Juan Carlos Oropeza May 20 '15 at 21:06
• @JuanCarlosOropeza `&` is a bitwise and. For `j=1`, the statement `i & 0b00010 >> 1` would mean do a bitwise and between i and the mask (`0b00010`) which will be either 2 or 0. The `>>` is a shift right 1 position. `0b00010` shifted to the right one gives you `0b00001` which is 1. 0 shifted is still 0. Likewise, `mask <<= 1` is a shift left and assignment. This is covered in msdn.microsoft.com/en-us/library/f96c63ed.aspx and msdn.microsoft.com/en-us/library/17zwb64t.aspx amd msdn.microsoft.com/en-us/library/vstudio/… – user40980 May 20 '15 at 21:13
• (I'm neither a C# nor a VB.net coder - though those references, I hope, should point you to the correct documentation either in Microsoft's references, or the necessary information to implement your own. Another refrence (not MS) for bit operators in C#: blackwasp.co.uk/CSharpShiftOperators.aspx ) `mask <<= 1` could be written as `mask *= 2`, but since I was working with bits it made more sense to read with bit shift operators. Likewise `>> j` could be written as `/ 2**j` but again, bit operations. – user40980 May 20 '15 at 21:16
• Yes, they help. I just need to test it. – Juan Carlos Oropeza May 20 '15 at 22:07
• I get back to study a litle more and found out why wasn't working. Is because operator precendence in C#. `(i & mask >> j)` should be `((i & mask) >> j)` – Juan Carlos Oropeza May 21 '15 at 16:23

This is my full answer. At the end didn't understand the `(i & mask >> j)`part so I use an IF. To see if the elem is part of the sum.

``````int[] elem = new int[] { 1, 2, 3, 4, 5 };
double maxElem = Math.Pow(2, elem.Length);

for (int first = 0; first < maxElem; first++)
{
int sum = 0;
for (int run = 0; run < elem.Length; run++)
{
if ((first & mask) > 0)
{
sum += elem[run];
}