2

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
3

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)
        mask <<= 1
    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
2

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 mask = 1;
    int sum = 0;
    for (int run = 0; run < elem.Length; run++)
    {
        if ((first & mask) > 0)
        {
            sum += elem[run];                    
        }
        mask <<= 1;
    }
    Debug.Write(sum + " - ");
 }

Result

0 - 1 - 2 - 3 - 3 - 4 - 5 - 6 - 4 - 5 - 6 - 7 - 7 - 8 - 9 - 10 - 5 - 6 - 7 - 8 - 8 - 9 - 10 - 11 - 9 - 10 - 11 - 12 - 12 - 13 - 14 - 15

  • This isn't a forum (one of the more awkward things to get one's head around). The best thing to do would be to leave a comment on an answer. And that if statement works just as well and given that you understand it, is likely more maintainable (thats good). – user40980 May 21 '15 at 2:32
  • @MichaelT Do you mean is wrong say thanks in my answer? If that is the case I'm sorry didn't tought as a bad thing and will remove it now. I create the answer to show full solution. – Juan Carlos Oropeza May 21 '15 at 2:37
  • I see two parts here - the "thanks" which isn't appropriate in an answer, and then the code, which isn't wrong to have here - just try to write it more as a stand alone post rather than a commentary on another answer. Hypothetically, if all of my posts were to disappear tomorrow (they won't), your post should be able to stand alone and be helpful to someone who reads it. – user40980 May 21 '15 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.