J

#### joeu2004

misstatements that I made.

Martin-888 said:Subject: List all combinations of 6/36 with unique 4 numbers

Date: Fri, 13 Jul 2012 11:09:25 +0000

Message-ID: <[email protected]>

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 said:Subject: Re: List all combinations of 6/36 with unique 4 numbers

Date: Sun, 15 Jul 2012 19:11:56 -0700

Message-ID: <[email protected]> [....]

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