Combin

[Andreas]

If I use =Combin(40,6) I get the result 3838380.

I would like to know which combination the numbers 3,12,17,24,32,36
represent without having to create all possible combinations and then
looking it up.

Any ideas?

Regards,
Andreas

 

[Mallycat]

What do you mean?

Are you saying you want to know =Combin(40,3) and =Combin(40,12) and
=Combin(40,17) etc etc?


If so, then use the Data Table feature

 

[Andreas]

Hi,

Thanks for the quick reply.

If I had the numbers 1, 2, 3, 4, 5, 6 then that is combination 1 of 3838380.

If I had the numbers 1, 2, 3, 4, 5, 7 then that is combination 2 of 3838380.

If I had the numbers 35, 36, 37, 38, 39, 40 then that is combination
3838380 of 3838380.

If I had the numbers 3, 12, 17, 24, 32, 36 then that is combination ????
of 3838380.

I am assuming that the combinations are always listed in ascending order.

Regards,
Andreas

 

[MartinW]

Hi Andreas,

Combin(40,6) is the excel way of saying 40C6 which is equal
to (40*39*38*37*36*35)/(6*5*4*3*2*1)

As far as I know there is no way of assigning a number or tag
to any of those combinations, it's just a simple calculation
of how many possibles there are.

You say that 1, 2, 3, 4, 5, 6 is combination 1 and 1, 2, 3, 4, 5, 7
is combination 2
But who is to say that 2,2,3,4,5,6 is not the logical second combination.

HTH
Martin

 

[Guest]

If I had the numbers 1, 2, 3, 4, 5, 6 then that is combination 1 of 3838380.
If I had the numbers 1, 2, 3, 4, 5, 7 then that is combination 2 of 3838380.
If I had the numbers 35, 36, 37, 38, 39, 40 then that is combination
3838380 of 3838380
If I had the numbers 3, 12, 17, 24, 32, 36 then that is combination ????
of 3838380
I am assuming that the combinations are always listed in ascending order

Here's one play to tinker with ..

1. We'll use a sub by Myrna Larson to generate all 3.8+ mil combinations in
the pick 6 out of 40 [COMBIN(40,6)]. Myrna's sub will list the combos
(strings) in ascending sequence down-then-across, zig-zagging from col A to
col B to col C ...

2. Then we'll use a UDF by Don Pistulka in a formula to derive the end
result for the strings to be queried

The play ..

Here's a link from my archives to a sample book*
with Myrna Larson's sub implemented:
http://savefile.com/files/1635536
MyrnaLarson_Combination_Permutation.xls
*Full details inside

Note: Save the file to your harddisk first, then open the file from there

In Sheet1, just make the settings as:
In A1: C
In B1: 6
Fill the numbers 1-40 within A3:A42
Select A1, then click the button ListPermutations to run Myrna's sub
**Leave it to run say, overnight (or longer)**

When the run's complete, the results will be written in a new sheet to the
left, with cols A to BF* filled with all the 3,838,380 combinations in
sequence such as:
*as COMBIN(40,6) = 3,838,380 combos,
divided by 65536 rows per col = 58.56 cols (col BF is the 58th col, from
left)

The results will be written in a new sheet (Sheet2) to the left

In Sheet2,

In A1:A65536 would be
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 7
1, 2, 3, 4, 5, 8
.....
1, 2, 18, 22, 23, 27
1, 2, 18, 22, 23, 28

In B1:B65536 (result in B1 continues from A65536)
1, 2, 18, 22, 23, 29
1, 2, 18, 22, 23, 30
....
1, 3, 18, 19, 23, 32
1, 3, 18, 19, 23, 33

In C1:C65536 (result in C1 continues from B65536)
1, 3, 18, 19, 23, 34
1, 3, 18, 19, 23, 35
....
and so on, in a zig-zag manner till just after mid-way down col BF

Name the output range in cols A to BF
Click Insert > Name > Define
Names in workbook: RData
Refers to: =Sheet2!$A:$BF

Then press Alt+F11 to go to VBE
Click Insert > Module
Copy n Paste the Functions (by Don Pistulka) below
into the code window on the right
(everything within the dotted lines)

'--------
Function RowN(myrange As Range, Myvalue)
For Each c In myrange.Cells
If c.Value = Myvalue Then
RowN = c.Row
Exit Function
Else
End If
Next c
RowN = "Not Found"
End Function

Function ColN(myrange As Range, Myvalue)
For Each c In myrange.Cells
If c.Value = Myvalue Then
ColN = c.Column
Exit Function
Else
End If
Next c
ColN = "Not Found"
End Function
'----------

Press Alt+Q to get back to Excel

In a new sheet,
list the combo strings to be queried in say, A1 down.

Eg:
1, 2, 18, 22, 24, 28
1, 3, 18, 19, 24, 33
1, 2, 18, 22, 24, 29
2, 8, 11, 24, 31, 34
1, 7, 16, 31, 32, 38
(with digits in ascending sequence, separated by a comma-space)

Then put in B1:
=IF(A1="","",65536*(ColN(RData,A1)-1)+RowN(RData,A1))
Copy B1 down
Col B will return the required results, viz.:

1, 2, 18, 22, 24, 28 65552
1, 3, 18, 19, 24, 33 131088
1, 2, 18, 22, 24, 29 65553
2, 8, 11, 24, 31, 34 851970
1, 7, 16, 31, 32, 38 327681


---

 

[Guest]

Typo in line:

In B1: 6

should read as:

In A2: 6

---

 

[Guest]

Apologies, some further typo corrections:

.. When the run's complete, the results will be written in a new sheet
to the left, with cols A to BF* filled with all the 3,838,380 combinations in ..

The above should read as ".. cols A to BG filled .." instead,
and hence the following defined range description:

Names in workbook: RData
Refers to: =Sheet2!$A:$BF

2nd line above should read as:

Refers to: =Sheet2!$A:$BG

Cols A to BF fully populated gives:
65536 x 58 = 3,801,088 combos only
so the remaining combos will be written to col BG
till last cell BG37292 (if my arithmetic is correct <g>)

---

 

[Biff]

Max, did you let the macro run to list all combinations? How long did it
take?

I tried it on my own file but I aborted after about 20 mins. I played around
with some other combos and it took only about a second to generate a set of
around 91K so I figured it wouldn't take that long to generate 3M. Wrong!

Biff

 

[Guest]

Max, did you let the macro run to list all combinations? How long did it
take?

Earlier, no (as you might have probably deduced from the descripts in my
responses to the OP <g>). But ... I just tried running it again here,
successfully!
The full works .. all 3,838,380 combos generated beautifully by Myrna's sub,
from A1 right up to BG37292 (yup, my arithmetic to calc the last cell in the
follow up response y'day was fine).

The resulting file is a huge 144 Mb (zipped to: 30 Mb)

I tried it on my own file but I aborted after about 20 mins. I played around
with some other combos and it took only about a second to generate a set of
around 91K so I figured it wouldn't take that long to generate 3M. Wrong!

The process above -- I ran it on a clean, fresh power down & re-boot (just
to be on the safe side) took around 30 mins to run on my sys: Pentium 1.86
GHz, 2 GB RAM, XP, xl2003


---

 

[Guest]

Here's the links to 2 sample books ..

A "full" version sample construct of the play is available at:
http://www.savefile.com/files/8377418
Combinations Generation & Lookup Output Sequence
Contains: Myrna's sub, Don's UDF, the *full* 3.8+ million combinations
output (Pick 6 out of 1 - 40) in Sheet2 and a lookup sheet with the formulas
to derive the sequence number of any combos within the 3.8+ million total
combinations.
[ It's a 29 MB zip d/l decompressing to 144 MB, file set to Manual calc mode ]

Alternatively, a much smaller-sized abridged version is available at:
http://www.savefile.com/files/7287459
Combos Gen n Lookup Output Sequence_Abridged_Ver
[ 1.1 MB zip decompressing to 6.2 MB, file set to Manual calc mode ]
Contents are the same as the full version (link above) except with an
abridged output (Pick 6 out of 1 - 40) in Sheet2:
First 2 cols only (65536 x 2 = 131,072 combos) instead of the full 58+ cols

Note: Save the file to your harddisk first, then open the file from there.
To facilitate testing, data input, etc the calc mode in the sample is
intentionally set to manual mode. Just press F9 to recalc / update as
required.

If I had the numbers 3, 12, 17, 24, 32, 36
then that is combination ???? of 3838380

Answer: It's combination# 1,405,869 (as derived in the full sample version)

---

 

[Dana DeLouis]

... took around 30 mins to run on my sys: Pentium 1.86

and as for the OP's sample question <g> ..
If I had the numbers 3, 12, 17, 24, 32, 36
then that is combination ???? of 3838380

Answer: It's combination# 1,405,869 (as derived in the full sample
version)

....The numbers {3, 12, 17, 24, 32, 36} out of 40 ???

Hi. As a side note, in the study of combinations, the op is asking for the
"Rank."
Because we are dealing with KSubsets, the op is asking for the Rank of a
particular KSubset. The function name is usually called "RankKSubset."
The solution code is called recursively using Combin. I get the same
solution as you in 0 seconds.
There are different ways to set it up...

Debug.Print RankKSubset(40, 3, 12, 17, 24, 32, 36)
1,405,869

--
HTH. :>)
Dana DeLouis
Windows XP, Office 2003

Here's the links to 2 sample books ..

A "full" version sample construct of the play is available at:
http://www.savefile.com/files/8377418
Combinations Generation & Lookup Output Sequence
Contains: Myrna's sub, Don's UDF, the *full* 3.8+ million combinations
output (Pick 6 out of 1 - 40) in Sheet2 and a lookup sheet with the
formulas
to derive the sequence number of any combos within the 3.8+ million total
combinations.
[ It's a 29 MB zip d/l decompressing to 144 MB, file set to Manual calc
mode ]

Alternatively, a much smaller-sized abridged version is available at:
http://www.savefile.com/files/7287459
Combos Gen n Lookup Output Sequence_Abridged_Ver
[ 1.1 MB zip decompressing to 6.2 MB, file set to Manual calc mode ]
Contents are the same as the full version (link above) except with an
abridged output (Pick 6 out of 1 - 40) in Sheet2:
First 2 cols only (65536 x 2 = 131,072 combos) instead of the full 58+
cols

Note: Save the file to your harddisk first, then open the file from there.
To facilitate testing, data input, etc the calc mode in the sample is
intentionally set to manual mode. Just press F9 to recalc / update as
required.

If I had the numbers 3, 12, 17, 24, 32, 36
then that is combination ???? of 3838380

Answer: It's combination# 1,405,869 (as derived in the full sample
version)

---

 

[Guest]

... The function name is usually called "RankKSubset."
The solution code is called recursively using Combin.
I get the same solution as you in 0 seconds.

Marvellous, Dana ! Thanks for dropping by, and confirming on the answer <g>.
Believe your solution is exactly what the OP was looking for here,
re OP's orig. post:

.. which combination the numbers 3,12,17,24,32,36 represent
without having to create all possible combinations
and then looking it up.

There are different ways to set it up...
Debug.Print RankKSubset(40, 3, 12, 17, 24, 32, 36)
1,405,869

Could you kindly post the function: RankKSubset ? Tried trawling google for
it but got no hits other than your earlier post in this thread. Thanks.

---

 

[Dana DeLouis]

Hi Max. Sure...Here is one way. I have it set up where the size of the set
is listed first. The size of the Subset is assumed from the remaining
numbers.
The output is:

1,405,869
0 Seconds

Sub TestIt()
Dim Start
Start = Timer
Debug.Print FormatNumber(RankKSubset(40, 3, 12, 17, 24, 32, 36), 0,
True)
Debug.Print Timer - Start & " Seconds"
End Sub

Function RankKSubset(Size, ParamArray v())
'//= = = = = = = = = = = = = = = = = =
'// By: Dana DeLouis
'//= = = = = = = = = = = = = = = = = =

Dim j As Long
Dim d As Double
Dim n As Double
Dim m As Double
Dim T As Double

With WorksheetFunction
m = Size
n = UBound(v) + 1
d = v(0)

T = T + .Combin(m, n) - .Combin(m - d + 1, n)
For j = 1 To UBound(v) - 1
m = m - d
n = n - 1
d = v(j) - v(j - 1)
T = T + .Combin(m, n) - .Combin(m - d + 1, n)
Next j
T = T + v(j) - v(j - 1)
End With
RankKSubset = T
End Function

If you are interested in this subject, one can also "UnRank" a number in a
similar fashion.
For example, the 3 Millionth combination in you large list is:

UnrankKSubset(3000000,6,40)

{9, 12, 22, 23, 27, 39}

 

[Guest]

.. Sure... Here is one way. I have it set up ...

Many thanks, Dana!
Works great

.. If you are interested in this subject,
one can also "UnRank" a number in a similar fashion.
For example, the 3 Millionth combination in you large list is:
UnrankKSubset(3000000,6,40)
{9, 12, 22, 23, 27, 39}

Yes, v.interested. Could you post a similar set-up for UnrankKSubset ?
Thanks.

---

 

[Tushar Mehta]

I imagine one could establish a convention for how combinations are numbered
and listed but AFAIK, there is no established sequence in which combinations
are enumerated. One could just as easily call 1,2,3,4,5,6 the 3838380th
combination or, for that matter, the 1901095th combination.

--
Regards,

Tushar Mehta
www.tushar-mehta.com
Excel, PowerPoint, and VBA add-ins, tutorials
Custom MS Office productivity solutions

 

[Dana DeLouis]

I imagine one could establish a convention for how combinations are

numbered

Hi. Some textbooks give the name "Lexicographical" order for the Op's
ordering of the subsets vs some version of a Gray Code order, or something
similar.

 

[Guest]

Hi Dana,

Perhaps you might have missed my response & request in the other branch ?

Could you post a similar set-up for UnrankKSubset ?

---

 

[Harlan Grove]

Dana DeLouis wrote...

Hi Max. Sure...Here is one way. I have it set up where the size of the set
is listed first. The size of the Subset is assumed from the remaining
numbers. ....
Function RankKSubset(Size, ParamArray v())
'//= = = = = = = = = = = = = = = = = =
'// By: Dana DeLouis
'//= = = = = = = = = = = = = = = = = =

....

UDF unnecessary. For sample size (k) 6, population size N, sample a
horizontal array, and using the following convenience defined names

rhseq ={6,5,4,3,2,1}

hlag1
={0,1,0,0,0,0;0,0,1,0,0,0;0,0,0,1,0,0;0,0,0,0,1,0;0,0,0,0,0,1;0,0,0,0,0,0}

the rank as you define it would be given by

=1+SUMPRODUCT(COMBIN(N-MMULT(s,hlag1),rhseq)-COMBIN(N+1-s,rhseq))

If you are interested in this subject, one can also "UnRank" a number in a
similar fashion.
For example, the 3 Millionth combination in you large list is:

UnrankKSubset(3000000,6,40)

{9, 12, 22, 23, 27, 39}

....

That may also be possible without a UDF, but I'm too lazy right now to
figure it out just not. Be easier to figure out each item in the
ordered sample in sequence rather than as a single array formula.

 

[Guest]

:
....

=1+SUMPRODUCT(COMBIN(N-MMULT(s,hlag1),rhseq)-COMBIN(N+1-s,rhseq))

Stratospheric ! Thanks for the enrichment, Harlan.

That may also be possible without a UDF, but I'm too lazy right now to
figure it out just not. Be easier to figure out each item in the
ordered sample in sequence rather than as a single array formula.

Interested in this part, too. Appreciate your suggestion on how to
reverse-derive the set of 6 from the rank. Thanks.

---

 

[Dana DeLouis]

Hi Max. There are a couple of ways to do it.
Given the op's initial question in reverse...

We are given 1,405,869 out of a possible 3,838,380.

We are first looking for x1 in {x1,_,_,_,_,_}.

We need to first sum the Combin's that don't exceed our number. We could
use code that works with the number (3838380 - 1405869), but we'll use
1405869 here.

Unfortunately, there is no Analytical solution to a Binomial Sum (Sum of
Excel's Combin function ) that allows a 1-liner for this particular problem.
(AFAIK!).
Therefore, we have to resort to a Loop. (Ahh!)

Here's a demo of the first number...

Sub Demo()
Dim n, k, m, j, t
Dim Rt ' Running Total
Dim Remem ' Remember

With WorksheetFunction
n = 1405869
k = 6
m = 40

Rt = 0
j = 1
Do
Remem = Rt
t = .Combin(m - j, k - 1)
Rt = Rt + t
j = j + 1
Loop While Rt < n
j = j - 1
MsgBox "First #: " & j
End With

End Sub

For out next loop, we adjust some values such as:
n = n - Remem 'Last total that didn't exceed #
m = m - j

Eventually, the count becomes the array.
3, 9, 5, 7, 8, 4
To convert it to our Subset, we take a running total again. (ie second
number is 3+9=12)
Therefore, our KSubset is (3,12,17,24,32,36).
Again, there are a few ways to do it.
Hope this general discussion helps.