Re: Total Combinations Matching a Set Sum

Looking at the algorithm quickly, it appears to do the following.

We could answer the question of how many sets of six numbers summing to
150 there are by generating all possible selections of six numbers and
counting how many sum to 150. To do this blindly would mean trying 49!
* 48! * 47! * 46! * 45! * 44! combinations. Therefore we want to cut
down the number of selections we look at.

The question asks for unique sets of six integers that sum to 150. The
set of numbers {31,40,30,25,22,2} is the same as the set of numbers
{2,22,25,30,31,40}, so we can reduce the search by only generating
numbers in ascending order. This is why the for loops go from the value
of the previous for loop:

For I = minval To (Target + 5) / 6 - 3
sum = sum + I
For J = I + 1 To (Target + 4 - sum) / 5 - 2
sum = sum + J

Now, why do we have the (Target+4-sum) / 5 - 2? Well, I'm too lazy to
do the exact calculations, but think of it this way. Let's say that we
have four numbers so far, and that these four numbers sum to 80. We
have 70 left to get to our target, and will add two more numbers to the
list. There is no point even considering adding numbers greater than or
equal to 35 to our set because since we're adding two more numbers in
ascending order to our set, the smallest total we can add at this stage
is 35 + 36 = 71. Since this is already large enough to go over 150, and
any other pair of numbers in ascending order starting from 35 will sum
to more than 71, we can stop that loop at 35. So we must have
Target-sum <= M+(M+1). The code:

For M = L + 1 To (Target + 1 - sum) / 2 - 1

is effectively doing that. If you think about it, the same time saving
can be applied in the other loops, but we need to consider that we will
be adding three numbers, four numbers, etc.

I don't see why the programmer didn't apply the same speedup to
starting values of the loops, at least for the few most innermost
loops. E.g. if we've added four numbers which sum to 80, the second to
most innermost loop must be at least 31, as 80+31+49=150.

Finally, think of the last if statement. If we've added up five
numbers, and they sum to less than 150 (which we know because otherwise
that code wouldn't be executing because of the way that the for loops
are designed), but we know that adding maxval takes us to 150 or
beyond, then there must be one and only one number x: M <= x <= maxval
such that adding the number to our current total will give 150. N is
that number, and we can check whether it is in the appropriate range
without actually counting through the options, saving us even more
time.

I suspect that there should be more efficient designs algorithms to
solve this problem. Having written this, I'm now hoping that this isn't
a plagiarised programming assignment that you have to attend a viva
for.

Cheers,

Ross-c

.

Relevant Pages

  • Re: Pythons simplicity philosophy
    ... > As to sum(), when learning string addition, ... the "summing strings" case instead, ... When the sequence is empty, ... 1000 loops, best of 3: ...
    (comp.lang.python)
  • Re: fminsearch error
    ... > The while loops works fine and my plots look good. ... The problem arises when I try to fit using one of my guesses. ... Because sum() adds up individual columns by default, the result of the above sum will be a 1x480 vector. ...
    (comp.soft-sys.matlab)
  • Re: Newbie Question about Fortran speed
    ... > than its counterpart with loops? ... With (extreme) pleasure - it might even open a few eyes enamored with le ... > things like SUM and the DO-ENDDO equivalent take exactly the same time to ...
    (comp.lang.fortran)
  • Re: doubles and ints
    ... Bill, could you persuade your news reader to quote correctly? ... from previous posts is your application domain) so this ... return sum / n; ... I've been needing for loops. ...
    (comp.lang.c)
  • Re: [PHP] array_sum($result)=100
    ... I have array of numbers and I want to get out of it a list of numbers ... calculate the sum of numbers in loops (end loop when the sum is larger ... It seems there is no algorithm can do this quickly. ...
    (php.general)