combination of numbers

[Mike__]

Harlan

I'm way out of my comfort zone for knowing what i'm taking about but could I
ask just a couple more questions.

In my example I'm only interested in 5 numbers pulled out of the master list

ie in the example below only these combnations are relevant

9 8 7 5 1
10 9 8 2 1
10 9 7 2 2
10 9 5 5 1
10 8 5 5 2
12 10 5 2 1
12 9 5 2 2
12 8 7 2 1
12 7 5 5 1

And these aren't

12 10 8
10 8 7 5
12 10 7 1
12 9 8 1
12 9 7 2
12 8 5 5
9 8 5 5 2 1
9 7 5 5 2 2
10 8 7 2 2 1
10 7 5 5 2 1
12 8 5 2 2 1

If it not too much hassle could you post a macro for me that will do this
for me.
I've simplified my actual real life problem by saying its 5 from 20. But its
actually 11 from about 150. Will the macro able to handle this or is there
too much number crunching involved ?

Thanks very much for your assistance so far.

Mike

Mike__ wrote...
....

Say I have 10 numbers, and some will be duplicated.

eg 1,2,2,5,5,7,8,9,10,12

How can I produce a list of combinations of say 5 numbers that add up to say
30.

I want my list to include ALL combinations

ie 1 2 8 9 10 will appear twice as it will use a different number 2.

I think I need Dana's macro mentioned previously but please enlighten me.

....

Dana never provided the code he used to produce his results. I
speculated that he used Mathematica to generate all nonempty
combinations, then summed each of them. If so, that's a relatively
simple operation in Mathematica because it includes built-in means to
generate combinations and sum the combinations. It's not as easy in
Excel.

Worst case, this class of problem requires checking all 2^N
combinations. It's a practical necessity to eliminate unnecessary
branches and reduce unnecessary duplication from the iterative process.
That's why my macro doesn't produce multiple identical combinations
when there are duplicate numbers in the original set. Doing so requires
additional overhead that grows with the number of combinations in each
iterative step.

If you took the output from my macro, you have the distinct
combinations that sum to the target value. Use Data > Text to Columns
to split those into separate columns. If your original set were in
J5:J14 and the parsed (Data > Text to Columns) distinct combinations
were in L5:Q24, you could calculate the number of instances in K5:K24
using the following formulas.

K5 [array formula]:
=PRODUCT(IF(COUNTIF($J$5:$J$14,L5:Q5),
COUNTIF($J$5:$J$14,L5:Q5)/COUNTIF(L5:Q5,L5:Q5)))

Select K5 and fill down into K6:K24.

The distinct combinations of your original data that sum to 30 are

12 10 8
10 8 7 5
12 10 7 1
12 9 8 1
12 9 7 2
12 8 5 5
9 8 7 5 1
10 9 8 2 1
10 9 7 2 2
10 9 5 5 1
10 8 5 5 2
12 10 5 2 1
12 9 5 2 2
12 8 7 2 1
12 7 5 5 1
9 8 5 5 2 1
9 7 5 5 2 2
10 8 7 2 2 1
10 7 5 5 2 1
12 8 5 2 2 1

and the number of instances of each using the col K formulas above are

1
2
1
1
2
1
2
2
1
1
2
4
2
2
1
2
1
1
2
2

Macros are the only way to generate the necessary combinations with
some efficiency. Formulas are more efficient counting the instances of
each of the distinct combinations in the solution set.

 

[Bernie Deitrick]

Mike,

There are approximately 5.94 x10^23 possible combinations of 11 numbers out of 150 numbers,
compared to 1.8 x 10^6 when you are dealing with 5 out of 20. If the 20 number problem took .001
second, the 150 number problem would take 10 million years....

HTH,
Bernie
MS Excel MVP

 

[Harlan Grove]

Mike__ wrote...
....

In my example I'm only interested in 5 numbers pulled out of the master list ....
If it not too much hassle could you post a macro for me that will do this
for me.

It's not the hassle, it's the point that if you can't modify the code,
how could you understand it? If you can't understand it, why would you
rely on it?

It's easy enough to extract the solution combinations with only 5
numbers from the exhaustive list, then calculate their respective
numbers of instances.

Finaly, I hate taking general code an making it overly particular.
However, if you don't want combinations of more than 11 numbers, change
the

For k = 2 To n

loop to

For k = 2 To 11

I've simplified my actual real life problem by saying its 5 from 20. But its
actually 11 from about 150. Will the macro able to handle this or is there
too much number crunching involved ?

It may take a LONG TIME, but if there's pronounced variance in your 150
number set, then many branches of combinations should be eliminated
quickly. However, it's impossible to say for sure whether my macro
would fail or not. Worst case, you won't have sufficient memory to
store the intermediate combinations.

Still, post your data and your target sum. If you don't post any
description of the numbers, they'd just be numbers.

 

[Harlan Grove]

Bernie Deitrick wrote...

There are approximately 5.94 x10^23 possible combinations of 11
numbers out of 150 numbers, compared to 1.8 x 10^6 when you are
dealing with 5 out of 20. If the 20 number problem took .001
second, the 150 number problem would take 10 million years....

Only if the target value were approximately equal to a random sum
of 11 of the largest half of the numbers would there be anything
close to this number of combinations actually generated. If the
target value were approximately equal to 11 times the average of
the 150 numbers, combinations involving more than a few of the
numbers below the 30th percentile or above the 70th percentile
would have been ruled out in shorter combinations. This assumes
a reasonable variance in the 150 numbers.

Also, if 80% of that 0.001 second runtime were overhead, it'd
only take a few million years. I suspect the OP would have run out
of RAM in his lifetime.

 

[Bernie Deitrick]

Only if the target value were approximately equal to a random sum
of 11 of the largest half of the numbers would there be anything
close to this number of combinations actually generated. If the
target value were approximately equal to 11 times the average of
the 150 numbers, combinations involving more than a few of the
numbers below the 30th percentile or above the 70th percentile
would have been ruled out in shorter combinations. This assumes
a reasonable variance in the 150 numbers.

Harlan,

I was guessing that the same sort of population statistics applied to both the 150 number set as the
20 number set, and that of the ~1sec (I may have blinked and mis-timed the routine), 99.9% was
overhead. (I didn't actually time it.) Still, even if the actual calc took only 1E-9 sec, it would
still take 10 years.... on a machine with unlimited memory. But I think we can agree that the
problem won't be solved on his PC anytime soon. And thanks, by the way, for the code. Works
sweetly.

Bernie

 

[Harlan Grove]

Bernie Deitrick wrote...
....

. . . Still, even if the actual calc took only 1E-9 sec, it would
still take 10 years.... on a machine with unlimited memory. But I
think we can agree that the problem won't be solved on his PC
anytime soon. . . .

I agree. This sort of problem is usually too big to be handled.
There's a small chance that the OP's data has a bit more variance
than the sample posted, in which case there's some likelihood that
huge swaths of combinations would be eliminated early on. Still, I'd
figure Excel would need to churn through billions of combinations,
and that'd probably take days.

BTW, COMBIN(150,11) returns 1.48852E+16. You claimed 5.94171E+23,
which is PERMUT(150,11). Since addition is commutative, there's no
difference between the sum of one permutation and another. So it's
only necessary to check distinct combinations. That drops your
original 10 million year runtime estimate down to the order of one
year. Any appreciable elimination of smaller cardinality combinations
would drop the runtime to the order of a single day or several hours.
At that order runtime, memory would be the limiting factor.

 

[Mike__]

These are the actual numbers I'm working with at the moment

A C 10
A D 20
A L 8
A S 1
AH 4
A Y 2
B M 8
C J 9
C P 11
C R 14
D K 6
D B 7
D D 8
D Z 0
D M 13
D V 9
E H 11
E D 13
F L 17
F Q 11
G H 12
G M 9
H P 4
J B 10
J C 10
J D 3
J P 15
J R 7
J S 0
J T 10
JA 0
J Z 2
JF 1
K D 3
K N 9
K P 6
L B 2
L M 0
L R 12
LT 7
M B 1
M Z 5
M D 9
M V 18
N H 10
O M 5
P C 9
P Z 11
P F 6
R E 1
R F 6
R K 2
R v 5
S A 3
S E 4
S K 3
S W 13
T H 17
T R 4
T S 7
T Z 15
U E 5
W G 12
W R 15


My aim is to find out all the combinations using 11 numbers that add up to
153.

If it would take far too long to run I could simplify it as below.

As 153 is at the top range,I don't believe that there would be many
combinations compared to the maximum amount possible.

It almost certainly uses AD 20 so perhaps I can look for 10 that total 133
and probably the lower numbers and duplicated numbers can be removed if its
still too unwieldy.

My data and total will change periodically -although my total will still be
very high- so would it be possible to type my total in cell A1 and my data
below it and then run the macro?

Thanks for all your help

MIke.

 

[Harlan Grove]

Mike__ wrote...

These are the actual numbers I'm working with at the moment ....
My aim is to find out all the combinations using 11 numbers that add up to
153.

I was affraid of something like this. Your largest 9 numbers alone add
up to 144, and that 9th largest number is the first of 3 13s. There are
6 9s and 4 0s, so there are 72 (=3*6*4) combinations using the largest
8 numbers, one of the 13s, one of the 9s and one of the 0s.

Off the top of my head, I'd guess the number of combinations of 11
numbers from your set of just 64 that'd sum to 153 would number on the
order of thousands, and it'd require trillions of combinations to
determine with certainty.

If it would take far too long to run I could simplify it as below.

As 153 is at the top range,I don't believe that there would be many
combinations compared to the maximum amount possible.

You're wrong. Intuition is useless for this sort of problem.

It almost certainly uses AD 20 so perhaps I can look for 10 that total 133
and probably the lower numbers and duplicated numbers can be removed if its
still too unwieldy.

Again, intuition is useless. 20 isn't needed.
SUM(18,17,17,15,15,15,14,13,13,13) equals 150, and there are 4 3s, so
there are 4 instances of

18,17,17,15,15,15,14,13,13,13,3

SUM(17,17,15,15,15,14,13,13,13,12) equals 144, and there are 3 12s and
6 9s, so there are 18 instances of

17,17,15,15,15,14,13,13,13,12,9

SUM(18,17,17,15,15,15,14,13,13) equals 137, and there are 3 13s, so 3
different combinations of these 9 numbers. There are 3 12s and 4 4s, so
36 combinations of

18,17,17,15,15,15,14,13,13,12,4

4 11s and 4 5s, so 48 combinations of

18,17,17,15,15,15,14,13,13,11,5

5 10s and 4 6s, so 90 combinations of

18,17,17,15,15,15,14,13,13,10,6

6 9s and 4 7s, so 72 combinations of

18,17,17,15,15,15,14,13,13,9,7

and 3 8s, so 9 combinations of

18,17,17,15,15,15,14,13,13,8,8

SUM(18,17,17,15,15,15,14,13) equals 124, and there are 3 13s, so 3
different combinations of these 8 numbers. There are 3 12s, 4 11s and 4
6s, so 144 instances of

18,17,17,15,15,15,14,13,12,11,6

That's enough for me. As I said, the number of combinations of 11
numbers that sum to 153 is on the order of thousands, and most of those
won't include 20. To repeat, INTUITION IS USELESS.

FWIW, my macro came up with 828 *distinct* combinations of 11 numbers
that sum to 153. Given the repeat counts for most of your 64 numbers,
I'd guess there were around 4,000 combinations in total.

 

[Mike__]

Mike__ wrote...

I was affraid of something like this. Your largest 9 numbers alone add
up to 144, and that 9th largest number is the first of 3 13s. There are
6 9s and 4 0s, so there are 72 (=3*6*4) combinations using the largest
8 numbers, one of the 13s, one of the 9s and one of the 0s.

Off the top of my head, I'd guess the number of combinations of 11
numbers from your set of just 64 that'd sum to 153 would number on the
order of thousands, and it'd require trillions of combinations to
determine with certainty.


You're wrong. Intuition is useless for this sort of problem.


Again, intuition is useless. 20 isn't needed.
SUM(18,17,17,15,15,15,14,13,13,13) equals 150, and there are 4 3s, so
there are 4 instances of

18,17,17,15,15,15,14,13,13,13,3

SUM(17,17,15,15,15,14,13,13,13,12) equals 144, and there are 3 12s and
6 9s, so there are 18 instances of

17,17,15,15,15,14,13,13,13,12,9

SUM(18,17,17,15,15,15,14,13,13) equals 137, and there are 3 13s, so 3
different combinations of these 9 numbers. There are 3 12s and 4 4s, so
36 combinations of

18,17,17,15,15,15,14,13,13,12,4

4 11s and 4 5s, so 48 combinations of

18,17,17,15,15,15,14,13,13,11,5

5 10s and 4 6s, so 90 combinations of

18,17,17,15,15,15,14,13,13,10,6

6 9s and 4 7s, so 72 combinations of

18,17,17,15,15,15,14,13,13,9,7

and 3 8s, so 9 combinations of

18,17,17,15,15,15,14,13,13,8,8

SUM(18,17,17,15,15,15,14,13) equals 124, and there are 3 13s, so 3
different combinations of these 8 numbers. There are 3 12s, 4 11s and 4
6s, so 144 instances of

18,17,17,15,15,15,14,13,12,11,6

That's enough for me. As I said, the number of combinations of 11
numbers that sum to 153 is on the order of thousands, and most of those
won't include 20. To repeat, INTUITION IS USELESS.

FWIW, my macro came up with 828 *distinct* combinations of 11 numbers
that sum to 153. Given the repeat counts for most of your 64 numbers,
I'd guess there were around 4,000 combinations in total.

 

[Mike__]

Have I lost my last message ?

 

[Mike__]

Aaaaargh

After spending 20 mins listing out exactly what my data consists of, I find
its been lost in the ether.

If I just could summarize, perhaps you could tell me if its worth continuing.

You told me earlier that my data would create about 4000 possible
combinations.

However what I didnt mention is that my raw data is split into 4 distinct
groups and my 11 numbers that will total 153 must have 1 from Group A and 4
from Group B and any combination from Group C & D as long as I finish with 11
numbers. So this will reduce the combinations down to a more workable amount.
(hopefully)

Is it worth me telling you which data is in which group, could you program a
model that i could sort my data into the separate groups,or has it just got
too complicated?

I'll understand if its the latter.

Mike

 

[Mike__]

Can you post your macro that would create about 4000 possibilities ?

Then I can leave you in peace !

Mike

 

[Dana DeLouis]

Hi. I can't add anything to the problem of using a fix size (ie 11 numbers)
from a larger size. Although I could have sworn I've read a technique
somewhere.
However, I thought I'd share an interesting technique for testing one's
program for selecting numbers that total a specific value.
Suppose one wanted to test a program with a large number of solutions.
One technique is to use a sequence of data 1,2,...n without duplicates.
For example, suppose we want to test our program to see if it will find all
combinations that total 153 from the numbers 1 thru 20.

One technique to calculate the number of solutions is to use the Generation
Function 1+z^i.
Excel can not do this of course, so we use a math program.
So, the real generation function goes out to our maximum value in our data
range. We take the product as i goes from 1 to 20.

gf = Product[1 + z^i, {i, 20}]

(1 + z)*(1 + z^2)*...(1 + z^19)*(1 + z^20)

We then look at the series expansion of this function, and pick the
coefficient associated with our z^153 term.

Timing[Coefficient[Series[gf, {z, 0, 153}], z, 153]]

{0.*Second, 3288}

So, we immediately see that the solution is 3288.
Given the numbers 1 thru 20, there are 3288 combinations that total 153.
And then we test our vba program to see if it finds all of them.

Stated another way, the above problem can also be worded from number theory
as "Given the number of Partitions of the integer 153 (of which there are
54,770,336,324), how many have unique solutions who's maximum value is 20?
Note that integer partitions have duplicates. For example, the partitions
of the number 4 are:
{4}, {3, 1}, {2, 2}, {2, 1, 1}, {1, 1, 1, 1}

Anyway, I just thought this might be interesting to share.

 

[Dana DeLouis]

I know this is an old thread, but I came across the generating function for
the following question if anyone is interested:

Given the numbers 1 - 20 (no duplicates), how many groups of 11 numbers
total 153?

gf = Product[x*y^j + 1, {j, 1, 20}]

There is no Series expansion in this version, but one would still want to
use a math program instead of Excel to do this.
m=20, n=11, t=153

Coefficient[Coefficient[Collect[Product[x*y^j+1,{j,m}],x],x,n],y,t]

As a function, there are 72 combinations of 11 numbers that total 153

Timing[Fx[20, 11, 153]]

{0.016*Second, 72}

Given the numbers 1-64, there are about 3.7 million combinations of 11
numbers that total 153. Timing seems slow, so I'm sure there's a more
efficient algorithm.

Timing[Fx[64, 11, 153]]

{2.5*Second, 3,699,726}

 

[ramshaker]

Mike__ wrote...

I was affraid of something like this. Your largest 9 numbers alone add
up to 144, and that 9th largest number is the first of 3 13s. There are
6 9s and 4 0s, so there are 72 (=3*6*4) combinations using the largest
8 numbers, one of the 13s, one of the 9s and one of the 0s.

Off the top of my head, I'd guess the number of combinations of 11
numbers from your set of just 64 that'd sum to 153 would number on the
order of thousands, and it'd require trillions of combinations to
determine with certainty.


You're wrong. Intuition is useless for this sort of problem.


Again, intuition is useless. 20 isn't needed.
SUM(18,17,17,15,15,15,14,13,13,13) equals 150, and there are 4 3s, so
there are 4 instances of

18,17,17,15,15,15,14,13,13,13,3

SUM(17,17,15,15,15,14,13,13,13,12) equals 144, and there are 3 12s and
6 9s, so there are 18 instances of

17,17,15,15,15,14,13,13,13,12,9

SUM(18,17,17,15,15,15,14,13,13) equals 137, and there are 3 13s, so 3
different combinations of these 9 numbers. There are 3 12s and 4 4s, so
36 combinations of

18,17,17,15,15,15,14,13,13,12,4

4 11s and 4 5s, so 48 combinations of

18,17,17,15,15,15,14,13,13,11,5

5 10s and 4 6s, so 90 combinations of

18,17,17,15,15,15,14,13,13,10,6

6 9s and 4 7s, so 72 combinations of

18,17,17,15,15,15,14,13,13,9,7

and 3 8s, so 9 combinations of

18,17,17,15,15,15,14,13,13,8,8

SUM(18,17,17,15,15,15,14,13) equals 124, and there are 3 13s, so 3
different combinations of these 8 numbers. There are 3 12s, 4 11s and 4
6s, so 144 instances of

18,17,17,15,15,15,14,13,12,11,6

That's enough for me. As I said, the number of combinations of 11
numbers that sum to 153 is on the order of thousands, and most of those
won't include 20. To repeat, INTUITION IS USELESS.

FWIW, my macro came up with 828 *distinct* combinations of 11 numbers
that sum to 153. Given the repeat counts for most of your 64 numbers,
I'd guess there were around 4,000 combinations in total.

 

[mellowe]

hi..sorry to jump in here but I think youse may be able to help me..I
have a column in excel that can list about 2,000 values (positive and
negative) to 2.d.p. I need excel to tell me which of these values add
up to a given value (x), it can be to the nearest whole number. I was
informed about using solver but it cant handle this many values..can
you help? can I use some sort of macro here?

 

[Anne Troy]

Hi, Mel. The only thing I've ever seen like this is here:
http://www.mrexcel.com/pc09.shtml
************
Anne Troy
www.OfficeArticles.com

 

[Albert]

I know that this is an old question but just in case someone needs a betteranswer: there is a new Excel Add in that can find combinations of numbers that add up to a target sum. The product is SumMatch from www.SumMatch.com.It has a trial version for 14 days and the cost of the full version is U$S30.-. This add in has digital processing technology instead of VBA macros what makes it faster that other solutions, it also covers All possible combinations of numbers that add up to a value, but it allows you to stop the calculations because in some cases the number of possible combinations is huge i.e.: if you have 30 numbers and you want to find combinations of groupsof 4 that add up to a value you need to calculate 15.7 million sums!
check www.SumMatch.com