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.