Combin

M

Max

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.
 
H

Harlan Grove

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!)
Click to expand...
....

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).
Click to expand...
....

Yup.
 
D

Dana DeLouis

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 said:
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!)
Click to expand...
...

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).
Click to expand...
...

Yup.
Click to expand...
 
M

Max

Dana DeLouis said:
.. Here's two cents on the vba version ..
Click to expand...

Bring me home on the vba version, Dana
I'm still interested in a full rendition of your UnrankKSubset
Thanks
 
M

Max

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 ..
 
Top