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
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
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
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
Mallycat wrote:
> 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
>
>
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
"Andreas" wrote:
> 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
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
Typo in line:
> In B1: 6
should read as:
> In A2: 6
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
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>)
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
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
"Max" <[email protected]> wrote in message
news:[email protected]...
> 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>)
> --
> Max
> Singapore
> http://savefile.com/projects/236895
> xdemechanik
> ---
"Biff" wrote:
> 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
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
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.
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)
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
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.
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)
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
> ... 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
"Max" <[email protected]> wrote in message
news:[email protected]...
> 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.
>
> 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)
> --
> Max
> Singapore
> http://savefile.com/projects/236895
> xdemechanik
> ---
"Dana DeLouis" wrote:
> ... 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.
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
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}
--
HTH. :>)
Dana DeLouis
Windows XP, Office 2003
"Max" <[email protected]> wrote in message
news:[email protected]...
> "Dana DeLouis" wrote:
>> ... 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.
> --
> Max
> Singapore
> http://savefile.com/projects/236895
> xdemechanik
> ---
"Dana DeLouis" wrote:
> .. 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.
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
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
In article <OpK3h#[email protected]>, [email protected] says...
> 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
>
>
> Mallycat wrote:
> > 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
> >
> >
>
>I imagine one could establish a convention for how combinations are
>numbered
>> If I had the numbers 1, 2, 3, 4, 5, 6 then that is combination 1.
>> If I had the numbers 1, 2, 3, 4, 5, 7 then that is combination 2.
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.
--
Dana DeLouis
Windows XP, Office 2003
"Tushar Mehta" <[email protected]> wrote in message
news:[email protected]...
>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
>
> In article <OpK3h#[email protected]>, [email protected]
> says...
>> 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
>>
>>
>> Mallycat wrote:
>> > 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
>> >
>> >
>>
Hi Dana,
Perhaps you might have missed my response & request in the other branch ?
> Could you post a similar set-up for UnrankKSubset ?
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
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.
"Harlan Grove" wrote:
....
> =1+SUMPRODUCT(COMBIN(N-MMULT(s,hlag1),rhseq)-COMBIN(N+1-s,rhseq))
Stratospheric ! Thanks for the enrichment, Harlan.
>>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.
Interested in this part, too. Appreciate your suggestion on how to
reverse-derive the set of 6 from the rank. Thanks.
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
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.
--
HTH. :>)
Dana DeLouis
Windows XP, Office 2003
"Max" <[email protected]> wrote in message
news:[email protected]...
> "Dana DeLouis" wrote:
>> .. 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.
> --
> Max
> Singapore
> http://savefile.com/projects/236895
> xdemechanik
> ---
Dana, thanks for the coaching! But I'm afraid it's beyond my depth (in both
vba and the underlying math) to follow through your guide-lines below and
transform your demo sub into a full working rendition. Could you lend a
helping hand ? Many thanks.
> 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).
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
Dana DeLouis wrote...
....
>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!)
....
Not necessarily.
Given N = 40, k = 6, fvseq defined as
=ROW(INDEX($1:$65536,1,1):INDEX($1:$65536,N-k+1,1))-1
(no volatile functions), and 1405869 in cell C7, x1 (in cell C8) is
given by the array formula
C8 [array formula]:
=MATCH(C7-1,MMULT(--(fvseq>=TRANSPOSE(fvseq)),
IF(fvseq,COMBIN(N+1-fvseq,COLUMNS(C$7:$H$7))
-COMBIN(N-fvseq,COLUMNS(C$7:$H$7)),0)))
The residual portion of q (in cell D7) is given by the array formula
D7 [array formula]:
=ROUND(C7-INDEX(MMULT(--(fvseq>=TRANSPOSE(fvseq)),
IF(fvseq,COMBIN(N+1-fvseq,COLUMNS(C$7:$H$7))
-COMBIN(N-fvseq,COLUMNS(C$7:$H$7)),0)),C8),0)
Rounding is necessary because Excel has a very nasty habit of returning
fractional values from COMBIN for various N and k values. The x2 value
(in cell D8) corresponding to this is given by the array formula
D8 [array formula]:
=MATCH(D7-1,IF(fvseq<N-COLUMNS(E$7:$H$7)-C8,
MMULT(--(fvseq>=TRANSPOSE(fvseq)),
IF(fvseq*(fvseq<N-COLUMNS(E$7:$H$7)-C8),
COMBIN(N+1-fvseq-C$8,COLUMNS(D$7:$H$7))
-COMBIN(N-fvseq-C$8,COLUMNS(D$7:$H$7)),0)),""))+C8
The next residual portion of q (in cell E7) is given by the array
formula
E7 [array formula]:
=ROUND(D7-INDEX(IF(fvseq<N-COLUMNS(E$7:$H$7)-C8,
MMULT(--(fvseq>=TRANSPOSE(fvseq)),
IF(fvseq*(fvseq<N-COLUMNS(E$7:$H$7)-C8),
COMBIN(N+1-fvseq-C$8,COLUMNS(D$7:$H$7))
-COMBIN(N-fvseq-C$8,COLUMNS(D$7:$H$7)),0)),""),D8-C8),0)
Fill E7 right into F7:H7, and fill D8 right into E8:G8. Complete this
by calculating x6 (in cell H8) with the simple formula
H8:
=G8+H7
>Therefore, our KSubset is (3,12,17,24,32,36).
....
Yup.
Sensational, Harlan!
Many thanks for sharing that with us ..
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
Hi Harlan. Wow! I have no idea how you translated this concept into
worksheet functions. Impressive.
Here's two cents on the vba version.
As j goes from 1 to 9, we sum the individual Combin's. We are looking for a
total that does not exceed our 'n value.
=COMBIN(40-j,6-1) j,1...9
However, the total sum equals the following 1-liner:
=(PERMUT(40,6)-PERMUT(40-9,6))/FACT(6)
However, this version requires 1 subtraction and 1 division in each loop.
Keeping a running total requires only 1 addition per loop.
That's why I think the above version is a little harder.
We could pre calculate some fixed values prior to each loop.
p=Permut(40,6)
f=Fact(6)
Then the equation becomes to find the maximum j that does not exceed n.
(p-Permut(m-j,k))/f < n
or if rearranged, the question becomes to find the "minimum" j that keeps
this equation true.
p-n*f < Permut(m-j,k)
This version works just as well, but I find that it's not as "simpler" as
the other version.
I can't think of a closed form of the above that can find a minimum j.
The only thing I can think of for "speed" would be to use the definition of
Permut in vba code, instead of Permut itself.
Anyway, thanks for your code. Interesting subject.!
--
Dana DeLouis
"Harlan Grove" <[email protected]> wrote in message
news:[email protected]...
> Dana DeLouis wrote...
> ...
>>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!)
> ...
>
> Not necessarily.
>
> Given N = 40, k = 6, fvseq defined as
>
> =ROW(INDEX($1:$65536,1,1):INDEX($1:$65536,N-k+1,1))-1
>
> (no volatile functions), and 1405869 in cell C7, x1 (in cell C8) is
> given by the array formula
>
> C8 [array formula]:
> =MATCH(C7-1,MMULT(--(fvseq>=TRANSPOSE(fvseq)),
> IF(fvseq,COMBIN(N+1-fvseq,COLUMNS(C$7:$H$7))
> -COMBIN(N-fvseq,COLUMNS(C$7:$H$7)),0)))
>
> The residual portion of q (in cell D7) is given by the array formula
>
> D7 [array formula]:
> =ROUND(C7-INDEX(MMULT(--(fvseq>=TRANSPOSE(fvseq)),
> IF(fvseq,COMBIN(N+1-fvseq,COLUMNS(C$7:$H$7))
> -COMBIN(N-fvseq,COLUMNS(C$7:$H$7)),0)),C8),0)
>
> Rounding is necessary because Excel has a very nasty habit of returning
> fractional values from COMBIN for various N and k values. The x2 value
> (in cell D8) corresponding to this is given by the array formula
>
> D8 [array formula]:
> =MATCH(D7-1,IF(fvseq<N-COLUMNS(E$7:$H$7)-C8,
> MMULT(--(fvseq>=TRANSPOSE(fvseq)),
> IF(fvseq*(fvseq<N-COLUMNS(E$7:$H$7)-C8),
> COMBIN(N+1-fvseq-C$8,COLUMNS(D$7:$H$7))
> -COMBIN(N-fvseq-C$8,COLUMNS(D$7:$H$7)),0)),""))+C8
>
> The next residual portion of q (in cell E7) is given by the array
> formula
>
> E7 [array formula]:
> =ROUND(D7-INDEX(IF(fvseq<N-COLUMNS(E$7:$H$7)-C8,
> MMULT(--(fvseq>=TRANSPOSE(fvseq)),
> IF(fvseq*(fvseq<N-COLUMNS(E$7:$H$7)-C8),
> COMBIN(N+1-fvseq-C$8,COLUMNS(D$7:$H$7))
> -COMBIN(N-fvseq-C$8,COLUMNS(D$7:$H$7)),0)),""),D8-C8),0)
>
> Fill E7 right into F7:H7, and fill D8 right into E8:G8. Complete this
> by calculating x6 (in cell H8) with the simple formula
>
> H8:
> =G8+H7
>
>>Therefore, our KSubset is (3,12,17,24,32,36).
> ...
>
> Yup.
>
"Dana DeLouis" wrote:
> .. Here's two cents on the vba version ..
Bring me home on the vba version, Dana
I'm still interested in a full rendition of your UnrankKSubset
Thanks
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
gawd, it's getting a bit lonely out here, stranded on 1st base, awaiting the
home run batter .. but perhaps the ballgame's over, I don't know, nobody told
me ..
--
Max
Singapore
http://savefile.com/projects/236895
xdemechanik
---
There are currently 1 users browsing this thread. (0 members and 1 guests)
Bookmarks