J
joeu2004
I am posting this "follow-up" to a previous discussion [1] to correct many
misstatements that I made.
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.
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/mic...g/browse_thread/thread/1f374f3bf2c4af86?hl=en.
[2] See my response to PeterT at 1:36 PM on July 15 Pacific Time at
https://groups.google.com/group/microsoft.public.excel.programming/msg/97df1687fc6f2d3a?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.
misstatements that I made.
Martin-888 said:
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 said:
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/mic...g/browse_thread/thread/1f374f3bf2c4af86?hl=en.
[2] See my response to PeterT at 1:36 PM on July 15 Pacific Time at
https://groups.google.com/group/microsoft.public.excel.programming/msg/97df1687fc6f2d3a?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.