XL 2003: How do I get every possible combination?

[Conan Kelly]

Cross-posted:
- microsoft.public.excel.programming
- microsoft.public.excel.worksheet.functions




Hello all,

I'm looking for an XL solution and/or a VBA solution...and I just can't wrap
my head around this.

I have a list of 162 numbers (loan amounts: min = $0, max = $3,107,000).

I want to find the sum of every single combination of the 162 numbers...from
one single number up to all 162 numbers. If my calculations are correct,
that is 26,244 different sums.

For VBA, I'm guessing I'm gonna need 2 for loops...one nested inside the
other. But I can't figure out the code to sum up all the different
combinations. Something like this:


For plngIndexX = LBound(pdblArray) To UBound(pdblArray)
For plngIndexY = LBound(pdblArray) To UBound(pdblArray)
'code to calculate all the differnt combinations
Next plngIndexY
Next plngIndexX


In XL, trying to think like a computer...I'm gonna need 162 bits(cells) to
calculate. But instead of each bit having a progressive value of a power of
2, each bit will be one of the numbers in my list. I was thinking of using
the list of numbers as column headers across the top, have a sumproduct
formula in column 163/164 that will sum up the column headers according to
the bits being on or off, and then have 26,000+ rows of bits marked on or
off. The problem would be filling out those 26,000 rows with 1's & 0's.
Anyone know of formulas or code that I could use to mark my bits on or off?

If it would be easier/faster in MS Access/SQL Server, I'm all ears.

Thanks for any help anyone can provide,

Conan Kelly



---------------------------
"Smokin' weed kills your brain cells. Drinkin' only screws up your
liver...ya got 2 a those."
- Earl Hickey (NBC's "My Name is Earl")


If Milli Vanilli falls in the woods, does someone else make a sound?

 

[Lars-Åke Aspelin]

Cross-posted:
- microsoft.public.excel.programming
- microsoft.public.excel.worksheet.functions




Hello all,

I'm looking for an XL solution and/or a VBA solution...and I just can't wrap
my head around this.

I have a list of 162 numbers (loan amounts: min = $0, max = $3,107,000).

I want to find the sum of every single combination of the 162 numbers...from
one single number up to all 162 numbers. If my calculations are correct,
that is 26,244 different sums.

For VBA, I'm guessing I'm gonna need 2 for loops...one nested inside the
other. But I can't figure out the code to sum up all the different
combinations. Something like this:


For plngIndexX = LBound(pdblArray) To UBound(pdblArray)
For plngIndexY = LBound(pdblArray) To UBound(pdblArray)
'code to calculate all the differnt combinations
Next plngIndexY
Next plngIndexX


In XL, trying to think like a computer...I'm gonna need 162 bits(cells) to
calculate. But instead of each bit having a progressive value of a power of
2, each bit will be one of the numbers in my list. I was thinking of using
the list of numbers as column headers across the top, have a sumproduct
formula in column 163/164 that will sum up the column headers according to
the bits being on or off, and then have 26,000+ rows of bits marked on or
off. The problem would be filling out those 26,000 rows with 1's & 0's.
Anyone know of formulas or code that I could use to mark my bits on or off?

If it would be easier/faster in MS Access/SQL Server, I'm all ears.

Thanks for any help anyone can provide,

Conan Kelly



---------------------------
"Smokin' weed kills your brain cells. Drinkin' only screws up your
liver...ya got 2 a those."
- Earl Hickey (NBC's "My Name is Earl")


If Milli Vanilli falls in the woods, does someone else make a sound?

There are 2^162-1 different combinations with one or several terms.
This is more than 5*10^48 combinations and thus not a problem that any
existing computer could solve.

Is there some other condition (restriction on the combinations) that
leads up to the 26000 combinations you state that you have?

Lars-Åke

 

[KC]

I must have misread the requirements.
If I have 4 numbers to sum,
from one single number - I have 4 numbers
from two numbers - I have 4 x 3 numbers
from three numbers - I have 4 x 3 x 2 numbers

why do I have only 2 loops for 162 numbers?

first number + 2nd number = 2nd number + first number
So I must also get rid of sums of equal values

 

[Martin Brown]

I must have misread the requirements.
If I have 4 numbers to sum,
from one single number - I have 4 numbers
from two numbers - I have 4 x 3 numbers
from three numbers - I have 4 x 3 x 2 numbers

But that still includes the same numbers in different orders and since
addition is commutative you can reduce the amount of work needed. It
doesn't help much but it does reduce things slightly from

O( N^(N+1/2) )

to a mere O(2^N )

Either way the computational difficulty of the problem increases
exponentially with the number of numbers you want to combine.

Given N distinct numbers taken M at a time the number of possible sums
that can be made is

s = N!/(M!(N-M!)

For your concrete example of 4 numbers this gives

N 0 1 2 3 4
s 1 4 6 4 1

Which as another poster pointed out yields 2^N-1 values.

why do I have only 2 loops for 162 numbers?

Because you don't have a clue what you are doing.

You would need 161 nested loops or a recursive implementation to do the
problem as stated and it would take a time much greater than the age of
the universe even on the worlds fastest machine.

It is a tractable problem only for relatively modest values of N,M.

If it is a homework question then you were probably meant to compute the
sum of every pair or something like that. N(N-1)/2

Regards,
Martin Brown

 

[KC]

I see you are confused that KC<>Conan Kelly

But that still includes the same numbers in different orders and since
addition is commutative you can reduce the amount of work needed. It
doesn't help much but it does reduce things slightly from

O( N^(N+1/2) )

to a mere O(2^N )

Either way the computational difficulty of the problem increases
exponentially with the number of numbers you want to combine.

Given N distinct numbers taken M at a time the number of possible sums
that can be made is

s = N!/(M!(N-M!)

For your concrete example of 4 numbers this gives

N 0 1 2 3 4
s 1 4 6 4 1

Which as another poster pointed out yields 2^N-1 values.

Because you don't have a clue what you are doing.

You would need 161 nested loops or a recursive implementation to do the
problem as stated and it would take a time much greater than the age of
the universe even on the worlds fastest machine.

It is a tractable problem only for relatively modest values of N,M.

If it is a homework question then you were probably meant to compute the
sum of every pair or something like that. N(N-1)/2

Regards,
Martin Brown

 

[Conan Kelly]

There are 2^162-1 different combinations with one or several terms.
This is more than 5*10^48 combinations and thus not a problem that any
existing computer could solve.

Is there some other condition (restriction on the combinations) that
leads up to the 26000 combinations you state that you have?

Lars-Åke

Lars-Åke,

Thank you for the feedback.

It's been a while since I've had a math class (and I didn't go very high in
math classes)...and, although I'm good at math, I'm definitely not a math
wiz. I just assumed that 162^2 was the number of possible combinations.
That is where the 26,000+ combinations came from.

Thanks again,

Conan

 

[Conan Kelly]

KC,

Thanks for the feedback.

No you didn't misread anything...my knowledge on problems like this aren't
has high as they should be.

Please see my response to Lars-Åke's post for more info.

Thanks again,

Conan

 

[Conan Kelly]

Martin Brown,

Because you don't have a clue what you are doing.

Thanks for the rudeness. By KC's response to your reply, I can see he
appreciates it as well. When you ASSUME, you make an ASS out of U and ME!!!

If you read my response to Lars-Åke's reply, you'll see that I'm am not as
ej-u-ma-cated as you (or ej-u-ma-cated enough to be tackling this problem)
and you can come back and post more condescending remarks.

Thanks again,

Conan

 

[Conan Kelly]

Martin Brown,

If it is a homework question then you were probably meant to compute the
sum of every pair or something like that. N(N-1)/2

If it was a homework problem, I would have a text book to look up the
correct process.

We have a client that has $28,000,000+ in loans in one category in June of
2006. They are telling me that $24,000,000+ are classified wrong and were
reclassified to another category in July 2006. For one reason or another,
they can't/didn't supply a list of loan ID numbers of the misclassified
loans. I was hoping to see if I could come up with a combination of loan
amounts to equal the $24,000,000+ number they supplied.

Thanks again,

Conan

 

[ytayta555]

Cross-posted:
I want to find the sum of every single combination of the 162 numbers...from
one single number up to all 162 numbers.  If my calculations are correct,
that is 26,244 different sums.

I had to work with some tips of combinations , If you desire you can
send
me your workbook with some more before / after examples , and I think
will
be ok .

 

[ker_01]

It's an interesting problem, and I agree that it is computationally
intensive. I do have one suggestion that could make it shorter, although I
still fear it would take a long time to run. Your best bet would still be to
push the client to give you their reclassification list.

Since you are comparing 28MM and 24MM, then rather than seeing what adds up
to 24MM you really only need to identify the 4MM that was correctly
classified (everything else is the reclassified items). You still have 162
recursive loops (there is a way to shorten this code with an array and two
separate subs, but it is still the same amount of processing), but just keep
a total as you add each value in each overall loop; as soon as you go over
4MM without hitting the exact target number, you know that you don't have the
right combination of items, and you can exit the loop and start back from the
top with the next combination/recursive loop.

Caveat: there may be multiple combinations that give you the exact
difference (4MM) so you will have to process all combinations even if you
find one that matches. If you don't have any way to then tell which
combination is correct, I have no idea where you go from there. 8-/

If you were 100% confident that there was only one accurate combination (but
how could you be?) you could also sort the values and start with the largest
values first (outermost recursive loops), because they will push your earlier
loops over 4MM with the least number of loops, which would also (potentially)
shorten your processing compared to starting with the smallest numbers first.

HTH
Keith

 

[Martin Brown]

Martin Brown,


If it was a homework problem, I would have a text book to look up the
correct process.

We have a client that has $28,000,000+ in loans in one category in June of
2006. They are telling me that $24,000,000+ are classified wrong and were
reclassified to another category in July 2006. For one reason or another,
they can't/didn't supply a list of loan ID numbers of the misclassified
loans. I was hoping to see if I could come up with a combination of loan
amounts to equal the $24,000,000+ number they supplied.

Be sure to get paid in cash for this work in advance. They are unlikely
to be in business much longer if they make mistakes like that.

The only chance you might have is to find a plausible solution by one of
the more advanced combinatorial methods like simulated annealing or a
greedy packing algorithm. They are considerably faster than brute force
but cannot guarantee to find the global optimum.

Comparing the active loans tags in June against July would seem a far
more logical way to proceed.

Regards,
Martin Brown

 

[ker_01]

Strangely, my reply yesterday shows as blank. Here is take #2

(1) I agree with previous posters that this sounds like a computationally
expensive macro, but I do think it is possible.

(2) Do you have figures for the loans and the overall disputed amount down
to the dollar? the penny? Or are you looking for a ballpark number?

(3) While you will have 162 recursive loops, you don't have to write them
all out. Write two subs; the first would call the second recursively through
each "layer". This will greatly simplify your code.

(3) You will have to process every possible combination to verify that there
isn't more than one combination that matches your expected results

(3) If you do have exact values ($24,017,826.13, etc), you either have to
match the 24MM or the 4MM (either one will give you the other as a remainder)
so focus on the 4MM. Add values but check the total value in each loop; once
you have exceeded the 4MM value you know that this can't be the correct
combination, and exit the loop and start the next combination of loans. If
you used 24MM as your matching value, you would do a lot more processing in
each loop.

HTH
Keith

 

[ker_01]

I'm only a casual user of the solver add-in, so I don't know if it has
limitations that might affect your outcome, but I just built a simple model
with 10 items with each just present or absent to hit a target value, and it
was fairly fast. Each additional item will slow it down exponentially, so
still expect it to take a while. One thing I like about the VBA solution is
that you can track how many iterations are complete, so you know the machine
isn't locked up and you can guestimate how much longer it will run.

Anyway, back to solver
* Place your values in column A (A1:A162)
* Leave column B blank (solver will be using these cells)
* In column C, set each cell in your range =A*B (e.g. C4 = A4*B4) so right
now, they will all equal zero
* Set D1= Sum(C:C)
* Set E1 = 0
* Set F1 = 1
*set solver to manipulate B1:B162, with the condition that B1:B162>=E1, add
condition B1:B162<=F1, add condition B1:B162= Integer' target cell is D1 and
should equal your 4MM value

as a casual user of solver I don't know if this gives you all possible
combinations, or if you just get the first one it matches, because when I use
it I only need one answer.

 

[Dana DeLouis]

Hi. Here are some tips for Solver...

* In column C, set each cell in your range =A*B (e.g. C4 = A4*B4) so right
now, they will all equal zero
* Set D1= Sum(C:C)

One technique is to removes these two steps and just use:
=SumProduct(A1:A163,B1:B163)

* Set E1 = 0
* Set F1 = 1
*set solver to manipulate B1:B162, with the condition that B1:B162>=E1, add
condition B1:B162<=F1, add condition B1:B162= Integer'

Slightly better is to remove these steps, and instead, add the one
constraint that B1:B163 are "Bin" (meaning 'Binary'). This
automatically limits B:B to 0 or 1 as you intended.

Don't forget to set the options to "Assume Linear" to increase the speed.

I'm only a casual user of the solver add-in, so I don't know if it has
limitations...

One limitation would be 200 Changing cells, but that's no problem here
with 163 changing cells.

= = = =
HTH :>)
Dana DeLouis