Very Difficult - Combination Generator

  • Thread starter Thread starter mark mason
  • Start date Start date
M

mark mason

I want to tell excel I have 5 items and want every possible combination
generated that has exactly four of them but these four may be all the
same all different or some the same some different. E.g.

Items = 1,2,3,4,5

Combination 1 = 1,1,1,1
Combination 2 = 1,1,1,2
Combination 54 = 2,1,5,3
Combination 120 = 5,4,1,1

Combination 89 = 1,1,2,1 - this is however a duplication of number 2
and therefore would not want this one.

Anyone help ?



------------------------------------------------




------------------------------------------------
 
Hi, Mark,

Here's one approach. In cell I1, put the value 5 and name that cell
"MAX_ITEMS". Put the value 1 into cells B1 through E1. Put this
formula into cell B2:

=IF(MIN(B1:$E1)=MAX_ITEMS,A2,IF(MIN(C1:$E1)=MAX_ITEMS,B1+1,B1))

and fill that formula across into C2 and D2 (but not E2).

Put this formula into E2:

=IF(E1=MAX_ITEMS,D2,E1+1)

Now fill down cells B1 through E1 (you need to fill down to row 70 to
get the whole series).

So, how does it work? Well, the E formula is easy. It says, add one
to the cell above me unless I reached the limit, in which case start
over - but not at one, at the cell next to me, because I want to never
be less than the one next to me (this is how we avoid duplication).

The formula for the other columns says, if all of the cells in the
preceding row, from my column to the end, are equal to MAX_ITEMS (this
because the formulas are written so no cell ever goes over MAX_ITEMS,
so if the MIN of the range is MAX_ITEMS and none is larger than
MAX_ITEMS, they must all be equal to MAX_ITEMS)... If all those cells
are equal to MAX_ITEMS, it's time to roll over this "digit of the
odometer". As with the E formula, we roll over to the value of the
cell to our left. If it's not time to roll over, then if it's time to
roll over the digit to our right, we need to increment this digit.
And if it's not time to roll either of these digits over, we leave
this digit alone and just copy the value above.

We start this whole business in column B because the formula needs to
refer to the cell to its left, which column A doesn't have. This way,
we can use the same formula in all of the first three columns, instead
of a different formula for the first column and columns 2 and 3.

Is that clear? I hope so.

Peace,
--Carl
 
Just an observation. If #89 is sorted (1,1,1,2), you say this is a
duplicate of #2 (1,1,1,2).
It looks to me that #120 (when sorted would be 1,1,4,5), is a duplicate of
an earlier 1,1,4,5.
Comb #54 would be a duplicate of an earlier 1,2,3,5...etc.
 
I want to tell excel I have 5 items and want every possible combination
generated that has exactly four of them but these four may be all the
same all different or some the same some different. E.g.

Items = 1,2,3,4,5

Combination 1 = 1,1,1,1
Combination 2 = 1,1,1,2
Combination 54 = 2,1,5,3
Combination 120 = 5,4,1,1

Combination 89 = 1,1,2,1 - this is however a duplication of number 2
and therefore would not want this one.
Click to expand...

By the logic in the last paragraph, combination 120 is also a repeat. In fact,
any combination in which earlier numbers are greater than any later number are
repeats. That is, a combination a,b,c,d is included only if a <= b, b <= c, and
c <= d.

That being the case, the first combination is trivial: 1 in each of A1:D1. Then
use the following formulas (a variation on Carl Manaste's approach).

A2: =IF(A1<N,A1+(B1>=N),#NUM!)
B2: =IF(B1<N,B1+(C1>=N),A2)
C2: =IF(C1<N,C1+(D1>=N),B2)
D2: =IF(D1<N,D1+1,C2)

Smaller formulas, fewer function calls, but otherwise same idea. For N = 5, this
gives 70 distinct combinations. Due to the conditional error return in the
column A formulas, it's easy to locate the last distinct combination.
 
Back
Top