Author 
Message 
moriman science forum beginner
Joined: 06 Apr 2006
Posts: 26

Posted: Mon Jul 17, 2006 12:21 am Post subject:
Stumped with figuring a formula...



Hi,
This is something I need to do for a lottery related project I'm working on.
I figured this years ago (changed poot and didn't keep a copy, sheesh) but
here goes..
In a 6 from 49 draw without replacement there are 13983816 combinations.
Imagine we call the first combination
01 02 03 04 05 06 combination number 0
then 01 02 03 04 05 43 would be combination number 37
and the final combination 44 45 46 47 48 49 would be combination number
13983815.
I want to be able to calculate the correct combination given a combination
number and vice versa.
So given combination 02 04 19 30 42 49
I would be able to calculate that it was combination number 1996088
or given combination number 3456789 I would be able to calculate that the
relevant combination was
03 05 11 35 43 44
I know the way I proceeded before was to subtract 01 02 03 04 05 06 from the
combination which left
combination number 0 = 00 00 00 00 00 00
combination number 37 = 00 00 00 00 00 37
combination number 1996088 = 01 02 16 26 37 43
combination number 3456789 = 02 03 08 31 38 38
combination number 13983815 = 43 43 43 43 43 43
but I can't remember how I came up with the formalu for converting
combination number to combination and vice versa.
To help any who want to have a go, here are some important conversions and a
few others at the end for checking...
(best viewed maximized)
combination normal adjusted
number combination combination
(with 01 02 03 04 05 06
subtracted)
0000000000 01 02 03 04 05 06 00 00 00 00 00 00
0000000043 01 02 03 04 05 49 00 00 00 00 00 43
0000000044 01 02 03 04 06 07 00 00 00 00 01 01
0000000989 01 02 03 04 48 49 00 00 00 00 43 43
0000000990 01 02 03 05 06 07 00 00 00 01 01 01
0000015179 01 02 03 47 48 49 00 00 00 43 43 43
0000015180 01 02 04 05 06 07 00 00 01 01 01 01
0000178364 01 02 46 47 48 49 00 00 43 43 43 43
0000178365 01 03 04 05 06 07 00 01 01 01 01 01
0001712303 01 45 46 47 48 49 00 43 43 43 43 43
0001712304 02 03 04 05 06 07 01 01 01 01 01 01
0013983815 44 45 46 47 48 49 43 43 43 43 43 43
and the few testers
0006000000 05 07 11 37 38 44 04 05 08 33 33 38
0007000000 06 07 17 32 39 41 05 05 14 28 34 35
0008000000 07 09 11 15 28 37 06 07 08 11 23 31
0009000000 08 12 15 17 29 45 07 10 12 13 24 39
Thanks for any help anyone can offer,
mori



There are 10 types of people in the world; those who understand binary and
those who don't 

Back to top 


William Elliot science forum Guru
Joined: 24 Mar 2005
Posts: 1906

Posted: Mon Jul 17, 2006 2:09 am Post subject:
Re: Stumped with figuring a formula...



On Mon, 17 Jul 2006, moriman wrote:
Quote:  This is something I need to do for a lottery related project I'm working on.
I figured this years ago (changed poot and didn't keep a copy, sheesh) but
here goes..
I don't give financial advise for free. If you want me to perfect your 
system, then you'll have to cut me in for half of your wins. Are you
willing to agree to that?
Quote:  In a 6 from 49 draw without replacement there are 13983816 combinations.
Imagine we call the first combination
01 02 03 04 05 06 combination number 0
then 01 02 03 04 05 43 would be combination number 37
and the final combination 44 45 46 47 48 49 would be combination number
13983815.
I want to be able to calculate the correct combination given a combination
number and vice versa.
So given combination 02 04 19 30 42 49
I would be able to calculate that it was combination number 1996088
or given combination number 3456789 I would be able to calculate that the
relevant combination was
03 05 11 35 43 44
I know the way I proceeded before was to subtract 01 02 03 04 05 06 from the
combination which left
combination number 0 = 00 00 00 00 00 00
combination number 37 = 00 00 00 00 00 37
combination number 1996088 = 01 02 16 26 37 43
combination number 3456789 = 02 03 08 31 38 38
combination number 13983815 = 43 43 43 43 43 43
but I can't remember how I came up with the formalu for converting
combination number to combination and vice versa.
To help any who want to have a go, here are some important conversions and a
few others at the end for checking...
(best viewed maximized)
combination normal adjusted
number combination combination
(with 01 02 03 04 05 06
subtracted)
0000000000 01 02 03 04 05 06 00 00 00 00 00 00
0000000043 01 02 03 04 05 49 00 00 00 00 00 43
0000000044 01 02 03 04 06 07 00 00 00 00 01 01
0000000989 01 02 03 04 48 49 00 00 00 00 43 43
0000000990 01 02 03 05 06 07 00 00 00 01 01 01
0000015179 01 02 03 47 48 49 00 00 00 43 43 43
0000015180 01 02 04 05 06 07 00 00 01 01 01 01
0000178364 01 02 46 47 48 49 00 00 43 43 43 43
0000178365 01 03 04 05 06 07 00 01 01 01 01 01
0001712303 01 45 46 47 48 49 00 43 43 43 43 43
0001712304 02 03 04 05 06 07 01 01 01 01 01 01
0013983815 44 45 46 47 48 49 43 43 43 43 43 43
and the few testers
0006000000 05 07 11 37 38 44 04 05 08 33 33 38
0007000000 06 07 17 32 39 41 05 05 14 28 34 35
0008000000 07 09 11 15 28 37 06 07 08 11 23 31
0009000000 08 12 15 17 29 45 07 10 12 13 24 39
Thanks for any help anyone can offer,
mori



There are 10 types of people in the world; those who understand binary and
those who don't :)



Back to top 


mensanator@aol.compost science forum Guru
Joined: 24 Mar 2005
Posts: 826

Posted: Mon Jul 17, 2006 2:37 am Post subject:
Re: Stumped with figuring a formula...



William Elliot wrote:
Quote:  On Mon, 17 Jul 2006, moriman wrote:
This is something I need to do for a lottery related project I'm working on.
I figured this years ago (changed poot and didn't keep a copy, sheesh) but
here goes..
I don't give financial advise for free. If you want me to perfect your
system, then you'll have to cut me in for half of your wins. Are you
willing to agree to that?

What are these "wins" of which you speak?
Quote: 
In a 6 from 49 draw without replacement there are 13983816 combinations.
Imagine we call the first combination
01 02 03 04 05 06 combination number 0
then 01 02 03 04 05 43 would be combination number 37
and the final combination 44 45 46 47 48 49 would be combination number
13983815.
I want to be able to calculate the correct combination given a combination
number and vice versa.
So given combination 02 04 19 30 42 49
I would be able to calculate that it was combination number 1996088
or given combination number 3456789 I would be able to calculate that the
relevant combination was
03 05 11 35 43 44
I know the way I proceeded before was to subtract 01 02 03 04 05 06 from the
combination which left
combination number 0 = 00 00 00 00 00 00
combination number 37 = 00 00 00 00 00 37
combination number 1996088 = 01 02 16 26 37 43
combination number 3456789 = 02 03 08 31 38 38
combination number 13983815 = 43 43 43 43 43 43
but I can't remember how I came up with the formalu for converting
combination number to combination and vice versa.
To help any who want to have a go, here are some important conversions and a
few others at the end for checking...
(best viewed maximized)
combination normal adjusted
number combination combination
(with 01 02 03 04 05 06
subtracted)
0000000000 01 02 03 04 05 06 00 00 00 00 00 00
0000000043 01 02 03 04 05 49 00 00 00 00 00 43
0000000044 01 02 03 04 06 07 00 00 00 00 01 01
0000000989 01 02 03 04 48 49 00 00 00 00 43 43
0000000990 01 02 03 05 06 07 00 00 00 01 01 01
0000015179 01 02 03 47 48 49 00 00 00 43 43 43
0000015180 01 02 04 05 06 07 00 00 01 01 01 01
0000178364 01 02 46 47 48 49 00 00 43 43 43 43
0000178365 01 03 04 05 06 07 00 01 01 01 01 01
0001712303 01 45 46 47 48 49 00 43 43 43 43 43
0001712304 02 03 04 05 06 07 01 01 01 01 01 01
0013983815 44 45 46 47 48 49 43 43 43 43 43 43
and the few testers
0006000000 05 07 11 37 38 44 04 05 08 33 33 38
0007000000 06 07 17 32 39 41 05 05 14 28 34 35
0008000000 07 09 11 15 28 37 06 07 08 11 23 31
0009000000 08 12 15 17 29 45 07 10 12 13 24 39
Thanks for any help anyone can offer,
mori



There are 10 types of people in the world; those who understand binary and
those who don't :)



Back to top 


William Elliot science forum Guru
Joined: 24 Mar 2005
Posts: 1906

Posted: Mon Jul 17, 2006 8:28 am Post subject:
Re: Stumped with figuring a formula...



On Sun, 16 Jul 2006, mensanator@aol.com wrote:
Quote:  William Elliot wrote:
On Mon, 17 Jul 2006, moriman wrote:
This is something I need to do for a lottery related project I'm working on.
I figured this years ago (changed poot and didn't keep a copy, sheesh) but
here goes..
I don't give financial advise for free. If you want me to perfect your
system, then you'll have to cut me in for half of your wins. Are you
willing to agree to that?
What are these "wins" of which you speak?
5 + i.10^8 


Back to top 


moriman science forum beginner
Joined: 06 Apr 2006
Posts: 26

Posted: Mon Jul 17, 2006 10:00 am Post subject:
Re: Stumped with figuring a formula...



"moriman" <morimanspamless@btinternet.com> wrote in message
news:DJGdnT1zdYGbRSfZRVnytQ@bt.com...
Quote:  Hi,
This is something I need to do for a lottery related project I'm working
on.
I figured this years ago (changed poot and didn't keep a copy, sheesh) but
here goes..
In a 6 from 49 draw without replacement there are 13983816 combinations.
Imagine we call the first combination
01 02 03 04 05 06 combination number 0
then 01 02 03 04 05 43 would be combination number 37
and the final combination 44 45 46 47 48 49 would be combination number
13983815.
I want to be able to calculate the correct combination given a combination
number and vice versa.
So given combination 02 04 19 30 42 49
I would be able to calculate that it was combination number 1996088
or given combination number 3456789 I would be able to calculate that the
relevant combination was
03 05 11 35 43 44
I know the way I proceeded before was to subtract 01 02 03 04 05 06 from
the
combination which left
combination number 0 = 00 00 00 00 00 00
combination number 37 = 00 00 00 00 00 37
combination number 1996088 = 01 02 16 26 37 43
combination number 3456789 = 02 03 08 31 38 38
combination number 13983815 = 43 43 43 43 43 43
but I can't remember how I came up with the formalu for converting
combination number to combination and vice versa.
To help any who want to have a go, here are some important conversions and
a
few others at the end for checking...
(best viewed maximized)
combination normal adjusted
number combination combination
(with 01 02 03 04 05 06
subtracted)
0000000000 01 02 03 04 05 06 00 00 00 00 00
00
0000000043 01 02 03 04 05 49 00 00 00 00 00
43
0000000044 01 02 03 04 06 07 00 00 00 00 01
01
0000000989 01 02 03 04 48 49 00 00 00 00 43
43
0000000990 01 02 03 05 06 07 00 00 00 01 01
01
0000015179 01 02 03 47 48 49 00 00 00 43 43
43
0000015180 01 02 04 05 06 07 00 00 01 01 01
01
0000178364 01 02 46 47 48 49 00 00 43 43 43
43
0000178365 01 03 04 05 06 07 00 01 01 01 01
01
0001712303 01 45 46 47 48 49 00 43 43 43 43
43
0001712304 02 03 04 05 06 07 01 01 01 01 01
01
0013983815 44 45 46 47 48 49 43 43 43 43 43
43
and the few testers
0006000000 05 07 11 37 38 44 04 05 08 33 33
38
0007000000 06 07 17 32 39 41 05 05 14 28 34
35
0008000000 07 09 11 15 28 37 06 07 08 11 23
31
0009000000 08 12 15 17 29 45 07 10 12 13 24
39
Thanks for any help anyone can offer,

ok, here's where I've got so far....
I'll use the adjusted values i.e. The combination minus 01 02 03 04 05 06
and number the individual numbers n0, n1, n2, n3, n4 & n5 where n5 is the
highest number
The first 43 only deal with n5 and are trivial...
00 00 00 00 00 00 > 0
..
00 00 00 00 00 24 > 24
..
00 00 00 00 00 43 > 43
The combinations where n4 > 0 can be calculated as follows
44*45/2  (44n4)*(45n4) + (n5n4)
so that...
n4 n5
00 00 00 00 03 19 = (44*45)/2  (41*42)/2 + 16 = combination 145
00 00 00 00 26 38 = (44*45)/2  (18*19)/2 + 12 = combination 831
when n3 = 1 we have
990*991/2  (990n3)*(991n3)/2 + (44n3)*(45n3)/2  (44n4)*(45n4)/2 +
(n5n4)
so that...
n3 n4 n5
00 00 00 01 07 23 = 990*991/2  (989*990)/2 + (43*44)/2  (37*3/2 + 16 =
1249
00 00 00 01 31 43 = 990*991/2  (989*990)/2 + (43*44)/2  (13*14)/2 + 12 =
1857
but the above formula falls apart when n3 > 1
00 00 00 02 07 18 = 990*991/2  (988*989)/2 + (42*43)/2  (37*3/2 + 11 =
2190
but it should be 2147 (43 too much)
00 00 00 07 23 37 = 990*991/2  (983*984)/2 + (37*3/2  (19*20)/2 + 14 =
7436
but it should be 6527 (909 too much)
So obviously there is a mistake in the second formula as it should be
correct for all 0 < n3 < 44
Any ideas?
mori 

Back to top 


Dana DeLouis science forum beginner
Joined: 06 Mar 2006
Posts: 37

Posted: Mon Jul 17, 2006 12:31 pm Post subject:
Re: Stumped with figuring a formula...



Quote:  So given combination 02 04 19 30 42 49
I would be able to calculate that it was combination number 1996088
or given combination number 3456789 I would be able to calculate that the
relevant combination was
03 05 11 35 43 44

Your test data checks with a math program:
RankKSubset[{2, 4, 19, 30, 42, 49}, 49]
1996088
UnrankKSubset[3456789, 6, 49]
{3, 5, 11, 35, 43, 44}
Here's one way. It's done with code, but perhaps the pattern can be seen on
this Excel Spreadsheet for [{2, 4, 19, 30, 42, 49}.
=COMBIN(49,6) COMBIN(492+1,6)
=COMBIN(47,5)  COMBIN(472+1,5)
=COMBIN(45,4)  COMBIN(4515+1,4)
=COMBIN(30,3)  COMBIN(3011+1,3)
=COMBIN(19,2)  COMBIN(1912+1,2)
=49421
=SUM(A1:A6)
(Returns 1996088)
Good Luck.

HTH. :>)
Dana DeLouis
"moriman" <morimanspamless@btinternet.com> wrote in message
news:DJGdnT1zdYGbRSfZRVnytQ@bt.com...
Quote:  Hi,
This is something I need to do for a lottery related project I'm working
on.
I figured this years ago (changed poot and didn't keep a copy, sheesh) but
here goes..
In a 6 from 49 draw without replacement there are 13983816 combinations.
Imagine we call the first combination
01 02 03 04 05 06 combination number 0
then 01 02 03 04 05 43 would be combination number 37
and the final combination 44 45 46 47 48 49 would be combination number
13983815.
I want to be able to calculate the correct combination given a combination
number and vice versa.
So given combination 02 04 19 30 42 49
I would be able to calculate that it was combination number 1996088
or given combination number 3456789 I would be able to calculate that the
relevant combination was
03 05 11 35 43 44
I know the way I proceeded before was to subtract 01 02 03 04 05 06 from
the
combination which left
combination number 0 = 00 00 00 00 00 00
combination number 37 = 00 00 00 00 00 37
combination number 1996088 = 01 02 16 26 37 43
combination number 3456789 = 02 03 08 31 38 38
combination number 13983815 = 43 43 43 43 43 43
but I can't remember how I came up with the formalu for converting
combination number to combination and vice versa.
To help any who want to have a go, here are some important conversions and
a
few others at the end for checking...
(best viewed maximized)
combination normal adjusted
number combination combination
(with 01 02 03 04 05 06
subtracted)
0000000000 01 02 03 04 05 06 00 00 00 00 00
00
0000000043 01 02 03 04 05 49 00 00 00 00 00
43
0000000044 01 02 03 04 06 07 00 00 00 00 01
01
0000000989 01 02 03 04 48 49 00 00 00 00 43
43
0000000990 01 02 03 05 06 07 00 00 00 01 01
01
0000015179 01 02 03 47 48 49 00 00 00 43 43
43
0000015180 01 02 04 05 06 07 00 00 01 01 01
01
0000178364 01 02 46 47 48 49 00 00 43 43 43
43
0000178365 01 03 04 05 06 07 00 01 01 01 01
01
0001712303 01 45 46 47 48 49 00 43 43 43 43
43
0001712304 02 03 04 05 06 07 01 01 01 01 01
01
0013983815 44 45 46 47 48 49 43 43 43 43 43
43
and the few testers
0006000000 05 07 11 37 38 44 04 05 08 33 33
38
0007000000 06 07 17 32 39 41 05 05 14 28 34
35
0008000000 07 09 11 15 28 37 06 07 08 11 23
31
0009000000 08 12 15 17 29 45 07 10 12 13 24
39
Thanks for any help anyone can offer,
mori



There are 10 types of people in the world; those who understand binary and
those who don't :)



Back to top 


matt271829news@yahoo.co. science forum Guru
Joined: 11 Sep 2005
Posts: 846

Posted: Mon Jul 17, 2006 1:01 pm Post subject:
Re: Stumped with figuring a formula...



moriman wrote:
Quote:  "moriman" <morimanspamless@btinternet.com> wrote in message
news:DJGdnT1zdYGbRSfZRVnytQ@bt.com...
Hi,
This is something I need to do for a lottery related project I'm working
on.
I figured this years ago (changed poot and didn't keep a copy, sheesh) but
here goes..
In a 6 from 49 draw without replacement there are 13983816 combinations.
Imagine we call the first combination
01 02 03 04 05 06 combination number 0
then 01 02 03 04 05 43 would be combination number 37
and the final combination 44 45 46 47 48 49 would be combination number
13983815.
I want to be able to calculate the correct combination given a combination
number and vice versa.
So given combination 02 04 19 30 42 49
I would be able to calculate that it was combination number 1996088
or given combination number 3456789 I would be able to calculate that the
relevant combination was
03 05 11 35 43 44

Let a1, a2, a3, a4, a5, a6 be the combination, with a1 < a2 < a3 < a4 <
a5 < a6. Then I think the corresponding sequence number is
C(49, 6)  C(49  a1, 6)  C(49  a2, 5)  C(49  a3, 4)  C(49  a4,
3)  C(49  a5, 2)  C(49  a6, 1)  1
with the proviso that C(x,y) = 0 when y > x.
To go from sequence number to combination I guess you just find the
largest a1, a2, a3 etc. in order such that the partial sum of the above
expression is less than or equal to the required sequence number. 

Back to top 


moriman science forum beginner
Joined: 06 Apr 2006
Posts: 26

Posted: Tue Jul 18, 2006 5:51 pm Post subject:
Re: Stumped with figuring a formula...



<matt271829news@yahoo.co.uk> wrote in message
news:1153141264.027903.118100@35g2000cwc.googlegroups.com...
Quote:  moriman wrote:
"moriman" <morimanspamless@btinternet.com> wrote in message
news:DJGdnT1zdYGbRSfZRVnytQ@bt.com...
Hi,
This is something I need to do for a lottery related project I'm
working
on.
I figured this years ago (changed poot and didn't keep a copy, sheesh)
but
here goes..
In a 6 from 49 draw without replacement there are 13983816
combinations.
Imagine we call the first combination
01 02 03 04 05 06 combination number 0
then 01 02 03 04 05 43 would be combination number 37
and the final combination 44 45 46 47 48 49 would be combination
number
13983815.
I want to be able to calculate the correct combination given a
combination
number and vice versa.
So given combination 02 04 19 30 42 49
I would be able to calculate that it was combination number 1996088
or given combination number 3456789 I would be able to calculate that
the
relevant combination was
03 05 11 35 43 44
Let a1, a2, a3, a4, a5, a6 be the combination, with a1 < a2 < a3 < a4
a5 < a6. Then I think the corresponding sequence number is
C(49, 6)  C(49  a1, 6)  C(49  a2, 5)  C(49  a3, 4)  C(49  a4,
3)  C(49  a5, 2)  C(49  a6, 1)  1

Hi,
Thx for the reply
Having checked the above (it's not what I came up with before) I found it
does indeed supply the correct answer
Unfortunately (as with Dana's reply) it would be difficult to implement as
the program I'm writing is in assembly language which doesn't have a
factorial function and as I'm using a doubleword limit (4294967295) each
calculation would have to check that I haven't exceeded this limit. I'm
doing it this way for speed as scanning through 13983816 combinations is a
sloooooooow process even with an assembly language program on a fast poot :(
Anyway, I managed to reinvent the wheel and rediscover the way I had
implemented it before
Here's the method I'm using (if you don't program yourself, espescially in
assembly, you'll probably find it hard to believe the processor speed issue
between division, multiplication, subtraction and addition, but division is
*incredibly* slow compared to multiplication which is also slow as compared
to addition or subtraction)
I will stick with your convention of a1...a6
I have the following 'lookup table'
level1:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,2
9,30,31,32,33,34,35,36,37,38,39,40,41,42,43
level2:
44,87,129,170,210,249,287,324,360,395,429,462,494,525,555,584,612,639,665,69
0,714,737,759,780,800,819,837,854,870,885,899,912,924,935,945,954,962,969,97
5,980,984,987,989
level3:
990,1936,2839,3700,4520,5300,6041,6744,7410,8040,8635,9196,9724,10220,10685,
11120,11526,11904,12255,12580,12880,13156,13409,13640,13850,14040,14211,1436
4,14500,14620,14725,14816,14894,14960,15015,15060,15096,15124,15145,15160,15
170,15176,15179
level4:
15180,29370,42614,54955,66435,77095,86975,96114,104550,112320,119460,126005,
131989,137445,142405,146900,150960,154614,157890,160815,163415,165715,167739
,169510,171050,172380,173520,174489,175305,175985,176545,177000,177364,17765
0,177870,178035,178155,178239,178295,178330,178350,178360,178364
level5:
178365,341550,490545,626296,749706,861636,962906,1054296,1136547,1210362,127
6407,1335312,1387672,1434048,1474968,1510928,1542393,1569798,1593549,1614024
,1631574,1646524,1659174,1669800,1678655,1685970,1691955,1696800,1700676,170
3736,1706116,1707936,1709301,1710302,1711017,1711512,1711842,1712052,1712178
,1712248,1712283,1712298,1712303
level6:
1712304,3246243,4616997,5838756,6924764,7887362,8738030,9487428,10145436,107
21193,11223135,11659032,12036024,12360656,12638912,12876248,13077624,1324753
5,13390041,13508796,13607076,13687806,13753586,13806716,13849220,13882869,13
909203,13929552,13945056,13956684,13965252,13971440,13975808,13978811,139808
13,13982100,13982892,13983354,13983606,13983732,13983788,13983809,13983815
and then simply do the following...
combination 03 07 19 30 42 49
subtract 01 02 03 04 05 06 respectively to get a new a1...a6
combination 02 05 16 26 37 43
(1) if a1 =0 then goto step 2, else store the number at that position in
level 6 (i.e. level6 number2 = 3246243)
then subtract the number at postion (a1) in level 5 (341550) giving
2904693
(2) if a2 = 1 then goto step 3, else add the number at that position in
level 5 (749706)
the subtract the number at postion (a2) in level 4 (66435) giving
3587964
(3) if a3 = 2 then goto step 4, else add the number at that position in
level 4 (146900)
the subtract the number at postion (a3) in level 3 (11120) giving
3723744
(4) if a4 = 3 then goto step 5, else add the number at that position in
level 3 (14040)
the subtract the number at postion (a4) in level 2 (819) giving 3736965
(5) if a5 = 4 then goto step 6, else add the number at that position in
level 2 (962)
the subtract the number at postion (a5) in level 1 (37) giving 3737890
(6) if a6 = 5 then finished else add the number at that position in level 6
(43) giving 3737933
So the whole thing can be done without multiplication or division ;)
Where do the numbersin the lookup table com from?
Well, level 1 is trivial
level 2 is 44, (44+43), (44+43+42), (44+43+42+41) ....
level 3 is sum(44:1), [sum(44:1) + sum(43:1)], [sum(44:1) + sum(43:1) +
sum(42:1)
I'm sure you get the drift from the above as levels 4 to 6 take up to much
room to explain, lol
Thx again,
mori
Quote:  with the proviso that C(x,y) = 0 when y > x.
To go from sequence number to combination I guess you just find the
largest a1, a2, a3 etc. in order such that the partial sum of the above
expression is less than or equal to the required sequence number.



Back to top 


moriman science forum beginner
Joined: 06 Apr 2006
Posts: 26

Posted: Tue Jul 18, 2006 5:53 pm Post subject:
Re: Stumped with figuring a formula...



"Dana" <ddelouis@bellsouth.net> wrote in message
news:3rLug.9357$Bx.2280@bignews5.bellsouth.net...
Quote:  So given combination 02 04 19 30 42 49
I would be able to calculate that it was combination number 1996088
or given combination number 3456789 I would be able to calculate that
the
relevant combination was
03 05 11 35 43 44
Your test data checks with a math program:
RankKSubset[{2, 4, 19, 30, 42, 49}, 49]
1996088
UnrankKSubset[3456789, 6, 49]
{3, 5, 11, 35, 43, 44}
Here's one way. It's done with code, but perhaps the pattern can be seen
on
this Excel Spreadsheet for [{2, 4, 19, 30, 42, 49}.
=COMBIN(49,6) COMBIN(492+1,6)
=COMBIN(47,5)  COMBIN(472+1,5)
=COMBIN(45,4)  COMBIN(4515+1,4)
=COMBIN(30,3)  COMBIN(3011+1,3)
=COMBIN(19,2)  COMBIN(1912+1,2)
=49421
=SUM(A1:A6)

Hi Dana
Thx for the reply
Having checked the above (it's not what I came up with before) I found it
does indeed supply the correct answer
Unfortunately (as with Matt's reply) it would be difficult to implement as
the program I'm writing is in assembly language which doesn't have a
factorial function and as I'm using a doubleword limit (4294967295) each
calculation would have to check that I haven't exceeded this limit. I'm
doing it this way for speed as scanning through 13983816 combinations is a
sloooooooow process even with an assembly language program on a fast poot :(
Anyway, I managed to reinvent the wheel and rediscover the way I had
implemented it before
Here's the method I'm using (if you don't program yourself, espescially in
assembly, you'll probably find it hard to believe the processor speed issue
between division, multiplication, subtraction and addition, but division is
*incredibly* slow compared to multiplication which is also slow as compared
to addition or subtraction)
I have the following 'lookup table'
level1:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,2
9,30,31,32,33,34,35,36,37,38,39,40,41,42,43
level2:
44,87,129,170,210,249,287,324,360,395,429,462,494,525,555,584,612,639,665,69
0,714,737,759,780,800,819,837,854,870,885,899,912,924,935,945,954,962,969,97
5,980,984,987,989
level3:
990,1936,2839,3700,4520,5300,6041,6744,7410,8040,8635,9196,9724,10220,10685,
11120,11526,11904,12255,12580,12880,13156,13409,13640,13850,14040,14211,1436
4,14500,14620,14725,14816,14894,14960,15015,15060,15096,15124,15145,15160,15
170,15176,15179
level4:
15180,29370,42614,54955,66435,77095,86975,96114,104550,112320,119460,126005,
131989,137445,142405,146900,150960,154614,157890,160815,163415,165715,167739
,169510,171050,172380,173520,174489,175305,175985,176545,177000,177364,17765
0,177870,178035,178155,178239,178295,178330,178350,178360,178364
level5:
178365,341550,490545,626296,749706,861636,962906,1054296,1136547,1210362,127
6407,1335312,1387672,1434048,1474968,1510928,1542393,1569798,1593549,1614024
,1631574,1646524,1659174,1669800,1678655,1685970,1691955,1696800,1700676,170
3736,1706116,1707936,1709301,1710302,1711017,1711512,1711842,1712052,1712178
,1712248,1712283,1712298,1712303
level6:
1712304,3246243,4616997,5838756,6924764,7887362,8738030,9487428,10145436,107
21193,11223135,11659032,12036024,12360656,12638912,12876248,13077624,1324753
5,13390041,13508796,13607076,13687806,13753586,13806716,13849220,13882869,13
909203,13929552,13945056,13956684,13965252,13971440,13975808,13978811,139808
13,13982100,13982892,13983354,13983606,13983732,13983788,13983809,13983815
and then simply do the following...
combination 03 07 19 30 42 49
subtract 01 02 03 04 05 06 respectively to get a new a1...a6
combination 02 05 16 26 37 43 (where a1=02, a2 = 05, a3=16 etc.)
(1) if a1 =0 then goto step 2, else store the number at that position in
level 6 (i.e. level6 number2 = 3246243)
then subtract the number at postion (a1) in level 5 (341550) giving
2904693
(2) if a2 = 1 then goto step 3, else add the number at that position in
level 5 (749706)
the subtract the number at postion (a2) in level 4 (66435) giving
3587964
(3) if a3 = 2 then goto step 4, else add the number at that position in
level 4 (146900)
the subtract the number at postion (a3) in level 3 (11120) giving
3723744
(4) if a4 = 3 then goto step 5, else add the number at that position in
level 3 (14040)
the subtract the number at postion (a4) in level 2 (819) giving 3736965
(5) if a5 = 4 then goto step 6, else add the number at that position in
level 2 (962)
the subtract the number at postion (a5) in level 1 (37) giving 3737890
(6) if a6 = 5 then finished else add the number at that position in level 6
(43) giving 3737933
So the whole thing can be done without multiplication or division ;)
Where do the numbersin the lookup table com from?
Well, level 1 is trivial
level 2 is 44, (44+43), (44+43+42), (44+43+42+41) ....
level 3 is sum(44:1), [sum(44:1) + sum(43:1)], [sum(44:1) + sum(43:1) +
sum(42:1)
I'm sure you get the drift from the above as levels 4 to 6 take up to much
room to explain, lol
Thx again,
mori
Quote:  (Returns 1996088)
Good Luck.

HTH. :>)
Dana DeLouis
"moriman" <morimanspamless@btinternet.com> wrote in message
news:DJGdnT1zdYGbRSfZRVnytQ@bt.com...
Hi,
This is something I need to do for a lottery related project I'm working
on.
I figured this years ago (changed poot and didn't keep a copy, sheesh)
but
here goes..
In a 6 from 49 draw without replacement there are 13983816 combinations.
Imagine we call the first combination
01 02 03 04 05 06 combination number 0
then 01 02 03 04 05 43 would be combination number 37
and the final combination 44 45 46 47 48 49 would be combination number
13983815.
I want to be able to calculate the correct combination given a
combination
number and vice versa.
So given combination 02 04 19 30 42 49
I would be able to calculate that it was combination number 1996088
or given combination number 3456789 I would be able to calculate that
the
relevant combination was
03 05 11 35 43 44
I know the way I proceeded before was to subtract 01 02 03 04 05 06 from
the
combination which left
combination number 0 = 00 00 00 00 00 00
combination number 37 = 00 00 00 00 00 37
combination number 1996088 = 01 02 16 26 37 43
combination number 3456789 = 02 03 08 31 38 38
combination number 13983815 = 43 43 43 43 43 43
but I can't remember how I came up with the formalu for converting
combination number to combination and vice versa.
To help any who want to have a go, here are some important conversions
and
a
few others at the end for checking...
(best viewed maximized)
combination normal adjusted
number combination combination
(with 01 02 03 04 05 06
subtracted)
0000000000 01 02 03 04 05 06 00 00 00 00 00
00
0000000043 01 02 03 04 05 49 00 00 00 00 00
43
0000000044 01 02 03 04 06 07 00 00 00 00 01
01
0000000989 01 02 03 04 48 49 00 00 00 00 43
43
0000000990 01 02 03 05 06 07 00 00 00 01 01
01
0000015179 01 02 03 47 48 49 00 00 00 43 43
43
0000015180 01 02 04 05 06 07 00 00 01 01 01
01
0000178364 01 02 46 47 48 49 00 00 43 43 43
43
0000178365 01 03 04 05 06 07 00 01 01 01 01
01
0001712303 01 45 46 47 48 49 00 43 43 43 43
43
0001712304 02 03 04 05 06 07 01 01 01 01 01
01
0013983815 44 45 46 47 48 49 43 43 43 43 43
43
and the few testers
0006000000 05 07 11 37 38 44 04 05 08 33 33
38
0007000000 06 07 17 32 39 41 05 05 14 28 34
35
0008000000 07 09 11 15 28 37 06 07 08 11 23
31
0009000000 08 12 15 17 29 45 07 10 12 13 24
39
Thanks for any help anyone can offer,
mori




There are 10 types of people in the world; those who understand binary
and
those who don't :)



Back to top 


Google


Back to top 



The time now is Mon Dec 10, 2018 9:31 pm  All times are GMT

