Reply
 
LinkBack Thread Tools Search this Thread Display Modes
  #1   Report Post  
Posted to microsoft.public.excel.programming
external usenet poster
 
Posts: 829
Default List 6-of-36 combinations matching 4 (errata)

I am posting this "follow-up" to a previous discussion [1] to correct many
misstatements that I made.


Martin-888 wrote:
Subject: List all combinations of 6/36 with unique 4 numbers
Date: Fri, 13 Jul 2012 11:09:25 +0000
Message-ID:

I would like Excel to give me all the possible combinations
of a 6/36 lottery, but only to win the 4 out of 6 numbers.

[....]
These wouldn't be valid [...] because "1 2 3 4" and "2 3 4 6"
are appearing twice.


I believe that Martin is asking for an "abbreviated wheel" of all 36 numbers
that guarantees a 4-of-6 win. An "optimal" abrreviated wheel would be a
minimum number of 6-of-36 combinations.

Originally, I had concluded that 2240 combinations are needed to satisfy the
requirements. Later, I "corrected" myself, saying that 5456 combinations
are needed.

But that was based on my misunderstanding of the objectives (see below).

As it turns out, 2240 is indeed the correct answer, although that might not
be (and probably is not) the minimum number.


From: "joeu2004"
Subject: List all combinations of 6/36 with unique 4 numbers
Date: Sun, 15 Jul 2012 19:11:56 -0700
Message-ID:

[....]
In order to generate the minimum number of combinations that
truly guarantees a match of 4 out of 6 drawn numbers, we must
allow some combinations to have duplicate quads. Again, see
my response to PeterT for details. [2]


That is incorrect.

The key is: it is not necessary to match __all__ 4-of-36 subsets in order
to guarantee a (at least one) 4-of-6 win. It is sufficient to match
__at_least__ one 4-of-6 subset in each 6-of-36 combination.

Moreover, for wheels of p numbers in general, it is not necessary to match
at least one 4-of-6 subset in __all__ 6-of-36 combinations. It is
sufficient to match at least one 4-of-6 subset in each __6-of-p__
combination, because wheels stipulate that their "guarantee" is valid only
if __all__ 6 drawn numbers are among the subset of p numbers. Thus, the
wheel "guarantee" is a __conditional__ guarantee.

In Martin's case, those are the same conditions because p is 36. But in
general, p is the size of smaller pool of numbers that the player chooses
from.

For example, a wheel of 18 numbers that guarantees at least one 4-of-6 win
requires only 42 combinations [3].

That relaxed requirement gives rise to an algorithm that does indeed ensure
there are no duplicate 4-of-6 subsets among the combinations that comprise
the wheel.

One algorithm "to wheel" p numbers is (6 <= p <= drawn numbers):

for each 6-of-p combination
if none of its fifteen 4-of-6 subsets is covered
by at least one combination in wheel
then add combination to wheel

For p=36, that algorithm does generate a wheel of 2240 combinations with no
duplicate 4-of-6 subsets.

They cover only 33,600 of the 58,905 4-of-36 combinations. But that is
sufficient because the algorithm ensures that there is a wheel combination
that covers at least one of the 4-of-6 combinations of each 6-of-p
combination.

For a VBA implementation, download "6-wheel.xls" from
https://www.box.com/s/86d798e46fdb6054d39e. The procedure genMyWheel does
the work. The procedures checkNumbers and checkCombos can be used to verify
correctness of the result.

However, that algorithm does not necessarily (and probably does not) find
the __minimum__ number of combinations the meet the wheel requirements. For
example, for a wheel of 18 numbers (p=18), that algorithm generates 104
combinations, not 42.

Moreover, it might also be noted that the 42-combination wheel has an even
distribution of the 18 numbers. The algorithm above does not guarantee
that; in fact, the actual result is far from it.

An algorithm to generate a (more) "optimal" wheel of p numbers is more
complicated to describe, much less to implement "efficiently" (TBD). One
such algorithm might be:

for each uncovered 6-of-p combination ("new combination")
if none of its fifteen 4-of-6 subsets is covered
by at least one combination in wheel
then
find uncovered combination ("best combination") that
covers the most uncovered combinations including
"new combination"
add "best combination" to wheel

The operative word is "efficiently".

It is not difficult to implement an inefficient algorithm. But there are
memory-v-time trade-offs that require careful consideration.

Challenges:

1. It is unclear to me whether that algorithm generates the __most__ optimal
wheel; that is, the fewest number of combinations.

2. I am having trouble finding a way to count (predict) the number of
combinations that we should expect in the (most) optimal wheel.

3. It is unclear to me how to ensure an even distribution of the p numbers
in the wheel, if that is even possible to guarantee (to the extent possible
due to quantization error).


-----
[1] See the previous thread with the subject "List all combinations of 6/36
with
unique 4 numbers" at
https://groups.google.com/group/micr...f2c4af86?hl=en.


[2] See my response to PeterT at 1:36 PM on July 15 Pacific Time at
https://groups.google.com/group/micr...fc6f2d3a?hl=en.


[3] For a 42-combination wheel of 18 numbers for a lottery that draws 6
numbers, see the interactive wheel generator at
http://www.smartluck.com/free-lotto-wheel-608js.htm.

  #2   Report Post  
Posted to microsoft.public.excel.programming
external usenet poster
 
Posts: 230
Default List 6-of-36 combinations matching 4 (errata)

On 20/07/2012 21:52, joeu2004 wrote:
I am posting this "follow-up" to a previous discussion [1] to correct many
misstatements that I made.


Martin-888 wrote:
Subject: List all combinations of 6/36 with unique 4 numbers
Date: Fri, 13 Jul 2012 11:09:25 +0000
Message-ID:

I would like Excel to give me all the possible combinations
of a 6/36 lottery, but only to win the 4 out of 6 numbers.

[....]
These wouldn't be valid [...] because "1 2 3 4" and "2 3 4 6"
are appearing twice.


I believe that Martin is asking for an "abbreviated wheel" of all 36
numbers
that guarantees a 4-of-6 win. An "optimal" abrreviated wheel would be a
minimum number of 6-of-36 combinations.

Originally, I had concluded that 2240 combinations are needed to satisfy
the requirements. Later, I "corrected" myself, saying that 5456
combinations are needed.

But that was based on my misunderstanding of the objectives (see below).

As it turns out, 2240 is indeed the correct answer, although that might
not be (and probably is not) the minimum number.



My representation of the problem used 64 bit integers with bit0 = 1 bit1
= 2 etc. Tables of the 4C36 and 6C36 were generated and then a fast
matching bits counting algorithm used to sift the most likely contenders
for an optimum. No guarantee that there isn't a better one.

The smallest subset I found was 2215 numbers with the first one being
the 64 bit seed numeric value 599 = 0x257 = { 1,2,3, 5, 7, 10 }

Deterministic search using the natural generated order of the ~2M 6C36
combos starting from 0x3F obtained by shifting the most significant bit
first and iterating over all six bits. Sanity check shows that there are
no free 6 digit combos that don't match at least one of these.

The OP would do well to note that only the Irish government have ever
been dumb enough to create a lottery scheme that was susceptible to this
particular method of attack.

--
Regards,
Martin Brown
  #3   Report Post  
Posted to microsoft.public.excel.programming
external usenet poster
 
Posts: 1
Default List 6-of-36 combinations matching 4 (errata)

On Friday, 20 July 2012 21:52:28 UTC+1, joeu2004 wrote:
I am posting this "follow-up" to a previous discussion [1] to correct many
misstatements that I made.


Martin-888 wrote:
Subject: List all combinations of 6/36 with unique 4 numbers
Date: Fri, 13 Jul 2012 11:09:25 +0000
Message-ID:

I would like Excel to give me all the possible combinations
of a 6/36 lottery, but only to win the 4 out of 6 numbers.

[....]
These wouldn't be valid [...] because "1 2 3 4" and "2 3 4 6"
are appearing twice.


I believe that Martin is asking for an "abbreviated wheel" of all 36 numbers
that guarantees a 4-of-6 win. An "optimal" abrreviated wheel would be a
minimum number of 6-of-36 combinations.

Originally, I had concluded that 2240 combinations are needed to satisfy the
requirements. Later, I "corrected" myself, saying that 5456 combinations
are needed.

But that was based on my misunderstanding of the objectives (see below).

As it turns out, 2240 is indeed the correct answer, although that might not
be (and probably is not) the minimum number.


From: "joeu2004"
Subject: List all combinations of 6/36 with unique 4 numbers
Date: Sun, 15 Jul 2012 19:11:56 -0700
Message-ID:

[....]
In order to generate the minimum number of combinations that
truly guarantees a match of 4 out of 6 drawn numbers, we must
allow some combinations to have duplicate quads. Again, see
my response to PeterT for details. [2]


That is incorrect.

The key is: it is not necessary to match __all__ 4-of-36 subsets in order
to guarantee a (at least one) 4-of-6 win. It is sufficient to match
__at_least__ one 4-of-6 subset in each 6-of-36 combination.

Moreover, for wheels of p numbers in general, it is not necessary to match
at least one 4-of-6 subset in __all__ 6-of-36 combinations. It is
sufficient to match at least one 4-of-6 subset in each __6-of-p__
combination, because wheels stipulate that their "guarantee" is valid only
if __all__ 6 drawn numbers are among the subset of p numbers. Thus, the
wheel "guarantee" is a __conditional__ guarantee.

In Martin's case, those are the same conditions because p is 36. But in
general, p is the size of smaller pool of numbers that the player chooses
from.

For example, a wheel of 18 numbers that guarantees at least one 4-of-6 win
requires only 42 combinations [3].

That relaxed requirement gives rise to an algorithm that does indeed ensure
there are no duplicate 4-of-6 subsets among the combinations that comprise
the wheel.

One algorithm "to wheel" p numbers is (6 <= p <= drawn numbers):

for each 6-of-p combination
if none of its fifteen 4-of-6 subsets is covered
by at least one combination in wheel
then add combination to wheel

For p=36, that algorithm does generate a wheel of 2240 combinations with no
duplicate 4-of-6 subsets.

They cover only 33,600 of the 58,905 4-of-36 combinations. But that is
sufficient because the algorithm ensures that there is a wheel combination
that covers at least one of the 4-of-6 combinations of each 6-of-p
combination.

For a VBA implementation, download "6-wheel.xls" from
https://www.box.com/s/86d798e46fdb6054d39e. The procedure genMyWheel does
the work. The procedures checkNumbers and checkCombos can be used to verify
correctness of the result.

However, that algorithm does not necessarily (and probably does not) find
the __minimum__ number of combinations the meet the wheel requirements. For
example, for a wheel of 18 numbers (p=18), that algorithm generates 104
combinations, not 42.

Moreover, it might also be noted that the 42-combination wheel has an even
distribution of the 18 numbers. The algorithm above does not guarantee
that; in fact, the actual result is far from it.

An algorithm to generate a (more) "optimal" wheel of p numbers is more
complicated to describe, much less to implement "efficiently" (TBD). One
such algorithm might be:

for each uncovered 6-of-p combination ("new combination")
if none of its fifteen 4-of-6 subsets is covered
by at least one combination in wheel
then
find uncovered combination ("best combination") that
covers the most uncovered combinations including
"new combination"
add "best combination" to wheel

The operative word is "efficiently".

It is not difficult to implement an inefficient algorithm. But there are
memory-v-time trade-offs that require careful consideration.

Challenges:

1. It is unclear to me whether that algorithm generates the __most__ optimal
wheel; that is, the fewest number of combinations.

2. I am having trouble finding a way to count (predict) the number of
combinations that we should expect in the (most) optimal wheel.

3. It is unclear to me how to ensure an even distribution of the p numbers
in the wheel, if that is even possible to guarantee (to the extent possible
due to quantization error).


-----
[1] See the previous thread with the subject "List all combinations of 6/36
with
unique 4 numbers" at
https://groups.google.com/group/micr...f2c4af86?hl=en.


[2] See my response to PeterT at 1:36 PM on July 15 Pacific Time at
https://groups.google.com/group/micr...fc6f2d3a?hl=en.


[3] For a 42-combination wheel of 18 numbers for a lottery that draws 6
numbers, see the interactive wheel generator at
http://www.smartluck.com/free-lotto-wheel-608js.htm.


BJ2020

Hello,
I realise this is an old thread, but hope someone will be able to help me.

I cannot download the spreadsheet "6-Wheel.xls" after clicking on the following link https://www.box.com/s/86d798e46fdb6054d39e.

On the box.com site after clicking the download button a small window opens stating "Your download is progressing" but nothing happens. I was logged into my google account at the time but do not have an account with box.com.

The spreadsheet was written by joeu2004, I have no means of contacting him to ask if he will enable me to download his program.

Really hope someone can help me

Regards
BJ2020
  #4   Report Post  
Posted to microsoft.public.excel.programming
external usenet poster
 
Posts: 1
Default List 6-of-36 combinations matching 4 (errata)

On Friday, 20 July 2012 21:52:28 UTC+1, joeu2004 wrote:
I am posting this "follow-up" to a previous discussion [1] to correct many
misstatements that I made.


Martin-888 wrote:
Subject: List all combinations of 6/36 with unique 4 numbers
Date: Fri, 13 Jul 2012 11:09:25 +0000
Message-ID:

I would like Excel to give me all the possible combinations
of a 6/36 lottery, but only to win the 4 out of 6 numbers.

[....]
These wouldn't be valid [...] because "1 2 3 4" and "2 3 4 6"
are appearing twice.


I believe that Martin is asking for an "abbreviated wheel" of all 36 numbers
that guarantees a 4-of-6 win. An "optimal" abrreviated wheel would be a
minimum number of 6-of-36 combinations.

Originally, I had concluded that 2240 combinations are needed to satisfy the
requirements. Later, I "corrected" myself, saying that 5456 combinations
are needed.

But that was based on my misunderstanding of the objectives (see below).

As it turns out, 2240 is indeed the correct answer, although that might not
be (and probably is not) the minimum number.


From: "joeu2004"
Subject: List all combinations of 6/36 with unique 4 numbers
Date: Sun, 15 Jul 2012 19:11:56 -0700
Message-ID:

[....]
In order to generate the minimum number of combinations that
truly guarantees a match of 4 out of 6 drawn numbers, we must
allow some combinations to have duplicate quads. Again, see
my response to PeterT for details. [2]


That is incorrect.

The key is: it is not necessary to match __all__ 4-of-36 subsets in order
to guarantee a (at least one) 4-of-6 win. It is sufficient to match
__at_least__ one 4-of-6 subset in each 6-of-36 combination.

Moreover, for wheels of p numbers in general, it is not necessary to match
at least one 4-of-6 subset in __all__ 6-of-36 combinations. It is
sufficient to match at least one 4-of-6 subset in each __6-of-p__
combination, because wheels stipulate that their "guarantee" is valid only
if __all__ 6 drawn numbers are among the subset of p numbers. Thus, the
wheel "guarantee" is a __conditional__ guarantee.

In Martin's case, those are the same conditions because p is 36. But in
general, p is the size of smaller pool of numbers that the player chooses
from.

For example, a wheel of 18 numbers that guarantees at least one 4-of-6 win
requires only 42 combinations [3].

That relaxed requirement gives rise to an algorithm that does indeed ensure
there are no duplicate 4-of-6 subsets among the combinations that comprise
the wheel.

One algorithm "to wheel" p numbers is (6 <= p <= drawn numbers):

for each 6-of-p combination
if none of its fifteen 4-of-6 subsets is covered
by at least one combination in wheel
then add combination to wheel

For p=36, that algorithm does generate a wheel of 2240 combinations with no
duplicate 4-of-6 subsets.

They cover only 33,600 of the 58,905 4-of-36 combinations. But that is
sufficient because the algorithm ensures that there is a wheel combination
that covers at least one of the 4-of-6 combinations of each 6-of-p
combination.

For a VBA implementation, download "6-wheel.xls" from
https://www.box.com/s/86d798e46fdb6054d39e. The procedure genMyWheel does
the work. The procedures checkNumbers and checkCombos can be used to verify
correctness of the result.

However, that algorithm does not necessarily (and probably does not) find
the __minimum__ number of combinations the meet the wheel requirements. For
example, for a wheel of 18 numbers (p=18), that algorithm generates 104
combinations, not 42.

Moreover, it might also be noted that the 42-combination wheel has an even
distribution of the 18 numbers. The algorithm above does not guarantee
that; in fact, the actual result is far from it.

An algorithm to generate a (more) "optimal" wheel of p numbers is more
complicated to describe, much less to implement "efficiently" (TBD). One
such algorithm might be:

for each uncovered 6-of-p combination ("new combination")
if none of its fifteen 4-of-6 subsets is covered
by at least one combination in wheel
then
find uncovered combination ("best combination") that
covers the most uncovered combinations including
"new combination"
add "best combination" to wheel

The operative word is "efficiently".

It is not difficult to implement an inefficient algorithm. But there are
memory-v-time trade-offs that require careful consideration.

Challenges:

1. It is unclear to me whether that algorithm generates the __most__ optimal
wheel; that is, the fewest number of combinations.

2. I am having trouble finding a way to count (predict) the number of
combinations that we should expect in the (most) optimal wheel.

3. It is unclear to me how to ensure an even distribution of the p numbers
in the wheel, if that is even possible to guarantee (to the extent possible
due to quantization error).


-----
[1] See the previous thread with the subject "List all combinations of 6/36
with
unique 4 numbers" at
https://groups.google.com/group/micr...f2c4af86?hl=en.


[2] See my response to PeterT at 1:36 PM on July 15 Pacific Time at
https://groups.google.com/group/micr...fc6f2d3a?hl=en.


[3] For a 42-combination wheel of 18 numbers for a lottery that draws 6
numbers, see the interactive wheel generator at
http://www.smartluck.com/free-lotto-wheel-608js.htm.


BJ2020

Hello,
I realise this is an old thread, but hope someone will be able to help me.

I cannot download the spreadsheet "6-Wheel.xls" after clicking on the following link https://www.box.com/s/86d798e46fdb6054d39e posted above by joeu2004.

On the box.com site after clicking the download button a small window opens stating "Your download is progressing" but nothing happens. I was logged into my google account at the time but do not have an account with box.com.

The spreadsheet was written by joeu2004, I have no means of contacting him to ask if he will enable me to download his program.

Please can someone can help me

Regards
BJ2020
Reply
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
List all combinations Bret Bernever Excel Programming 0 December 16th 09 10:36 PM
how can i get a list of combinations? Pastor Pudge Excel Discussion (Misc queries) 1 December 25th 08 09:45 PM
Can excel list combinations BOJO Excel Worksheet Functions 1 July 26th 07 12:26 AM
Matching Combinations Rothman Excel Worksheet Functions 1 March 27th 06 08:34 PM
List all possible combinations Spencer Hutton Excel Programming 1 January 13th 05 08:53 PM


All times are GMT +1. The time now is 09:02 PM.

Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright ©2004-2024 ExcelBanter.
The comments are property of their posters.
 

About Us

"It's about Microsoft Excel"