List all combinations of 6/36 with unique 4 numbers

[joeu2004]

I couldn't find a README FIRST

My bad! I neglected to update the uploaded file after I added the "README
FIRST" worksheet. I just did for posterity. But as you say, it is
unnecessary now that you found your mistake.

You didn't appear to be entirely confirdent about yours
either at the time.

I always leave open the possibility that I make mistakes. I did not have
then the tools to double-check. I do now.

And it appears that I did indeed make a mistake.

I had interpreted Martin's problem to be: find all combinations of 6 of 36
numbers such that each contains unique subsets of 4 numbers; that is, so
that no 4-number subset ("quad") is repeated. (Call this Problem #1.)

And Martin's example seems to indicate that he also thought that is a
necessary and sufficient condition to achieve his real goal. He wrote:
"These wouldn't be valid [...] because 1 2 3 4 and 2 3 4 6 are appearing
twice".

To that end, I believe that 2240 is the correct number of combinations for
Problem #1, and my original algorithm finds them all.

-----

However, now we believe that Martin's real goal is a "full wheel" of all 36
numbers. Thus, he wants to find the __minimum__ set of combinations of 6 of
36 numbers needed to guarantee matching at least 4 of 6 numbers drawn.
(Call this Problem #2.)

Indeed, that is closer to what Martin wrote in the first place, to wit:
"all the possible combinations of a 6/36 lottery, but only to win the 4 out
of 6 numbers".

The two problems are not the same(!). And the solution to one problem is
not also a solution to the other.

I believe 5456 is the correct number of combinations for Problem #2.

-----

As we know, the number of combinations of 4 of 36 numbers is 58,905. That
is, COMBIN(36,4).

But the 2240 combinations that solve Problem #1 cover only 33,600 of those
58,905 combinations.

For example, 1 3 5 29 is not covered. This is because for the combination 1
3 5 29 x y, all of the other quads are already covered in the first 2240
combinations, and the requirements for Problem #1 do not permit repeating
any quad.

I have implemented a solution for Problem #2. I don't know if it is a
"good" solution. I would prefer a better algorithm. But it does seem to
work.

Basically, I iterate over all COMBIN(36,6) combinations (1,974,792) 15 times
allowing for an increasing number (0 to 14) of duplicate quads. 15 is the
number of quads in each combination, namely COMBIN(6,4).

So each new combination covers as many new quads as possible, with the
fewest number of duplicate quads.

Thus, the first iteration finds the 2240 combinations that solve Problem #1;
the second iteration adds 139 combinations that cover 14 new quads; etc.

The combinations found in this manner do cover all 58,905 combinations of 4
of 36 numbers.

And I believe that approach does find the minimum number of combinations.
But I cannot prove it.

Although I am not happy with the multiple iterations over the nearly 2
million combinations, the run time for the solution for Problem #2 is "only"
about 129 seconds on my computer. (YMMV.)

 

[Peter T]

I had interpreted Martin's problem to be: find all combinations of 6 of
36 numbers such that each contains unique subsets of 4 numbers; that is,
so that no 4-number subset ("quad") is repeated. (Call this Problem #1.)

Me too.

However, now we believe that Martin's real goal is a "full wheel" of all
36 numbers. Thus, he wants to find the __minimum__ set of combinations of
6 of 36 numbers needed to guarantee matching at least 4 of 6 numbers
drawn. (Call this Problem #2.)

Really, why, has he said that? (I'm using a newsreader and can't see
anything about that)

Afraid I don't follow the objective yet alone the approach or solution
described below (mostly snipped as only one more comment for the moment),
but it's late here, maybe tomorrow.

Basically, I iterate over all COMBIN(36,6) combinations (1,974,792) 15
times allowing for an increasing number (0 to 14) of duplicate quads. 15
is the number of quads in each combination, namely COMBIN(6,4).

Well that's what mine was doing, but a LOT more times that that, which is
why it was so slow, even with some a few things to bail out early if no
point continuing.

Although I am not happy with the multiple iterations over the nearly 2
million combinations, the run time for the solution for Problem #2 is
"only" about 129 seconds on my computer. (YMMV.)

Probably not worth busting a gut for something that will only ever need to
run once to produce a single listing!

(yeah I know!)

Regards,
Peter T

 

[joeu2004]

I think joeu is right, it is 2240 tickets that I would need
to make sure that I win 4 out of 6

Actually, the correct number is 5456. For details, see my response to
PeterT at 1:36 PM on July 15 Pacific Time.

In a nutshell, I believe we are discussing two different problems. Problem
#1: find all combinations with unique sets of 4-number subsets ("quads").
Problem #2: find the minimum number of combinations that guarantees
matching 4 of 6 drawn numbers.

I think we both assumed that a solution to Problem #1 is also a solution to
Problem #2.

Now I realize that is incorrect. 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.

Here is the link of the game:
http://tinyurl.com/7pvqqwe

They may have rounded the chances of win to 320 from a
different number... since you guys cannot get to 320.

Oh, I can compute __that__ probability very easily.

The important thing is: that probability is very different from the
conditional probability for full and abbreviated wheels, which I had thought
your were referring to.

The probability 1/320 has nothing to do with the minimum number of
combinations that guarantees matching 4 of 6 drawn numbers.

Moreover, when you see probabilities like 1/320, it usually does not mean
that we have counted only 320 of something. Instead, it is usually the
result of dividing one number by another.

In this case, there are 6090 ways to match 4 of 6 drawn numbers, and there
are 1,947,792 total combinations of 6 of 36 numbers, what the player
chooses.

So the probablility is 6090/1947792. Equivalently, the denominator of the
odds ("1 out of ...") is 1947792/6090, which is about 319.83. That's where
1/320 comes from.

(The obvious rounding was never an issue.)

-----

For the benefit of anyone who might want some mathematical details, the key
to counting 6090 lies in the procedure for this particular lottery, Canada's
"Jour de Paye".

The lottery (not the player) actually draws 7 of 36 numbers, not just 6 of
36. The 7th number is designated as a "bonus" number. When the lottery
speaks of matching "4 of 6", they mean 4 of the first 6 drawn numbers. When
they speak of matching "4 of 6 plus bonus", they mean that the player's 6
numbers includes 4 of the first 6 drawn numbers and the 7th bonus number.

(Note: This is very different from the powerball-type lotteries that I am
familiar with, where the bonus ball is drawn from a separate set of numbers,
and the player chooses a bonus number in addition to the "normal" numbers,
just as the lottery does.)

Consequently, the number of ways to match 4 of 6 drawn numbers (and not the
bonus) is COMBIN(6,4)*COMBIN(29,2).

That is: the number of ways to match 4 of 6 drawn numbers, times the number
of ways to choose 2 more numbers (for a total of 6) from the set of numbers
that does not include any of the 7 drawn numbers (29 = 36 - 7).

Note: The count 6525 that I posted before was calculated by
COMBIN(6,4)*COMBIN(30,2). That would be correct if the lottery drew only 6
balls. I was unaware of the "Jour de Paye" procedures until now, when
Martin finally provided the link to the game.

 

[joeu2004]

I think joeu is right, it is 2240 tickets that I would need
to make sure that I win 4 out of 6

Actually, the correct number is 5456. [....]
there are 6090 ways to match 4 of 6 drawn numbers, and there are 1,947,792
total combinations of 6 of 36 numbers, what the
player chooses. So the probability is 6090/1947792.

I suspect those two statements might cause some confusion. Let me
clarify....

There are 6090 combinations that match 4 of a __specific__ 6 drawn numbers.

But we need 5456 combinations (carefully chosen) to match at least 4 of
__all_possible__ 6 drawn numbers.

 

[Peter T]

For example, 1 3 5 29 is not covered.

Ah, OK, so I had a go, and came up with 57725 6-number cominations.
Obviously that's not right but FWIW this is what I did -

Make the 58905 4-number combinations, from each make single 'long' 7 or 8
digit numbers, eg for 1,2,3,4 = 1020304, and make a lookup table of the 59k
single 'long' numbers

Make a similar listing of the 1.9m 6-number combinations, and make 3
equivalent 'long' numbers with each, eg for 1,2,3,4,5,6 make
1020304 : 2030405 : 3040506

look-up each of the 3 x 1.9 'long' numbers up in the list of 59k and return
the index

If the index is not already marked (in a 1-59k boolean array) as found add
the 6 numbers to an array. As mentioned it returns a qty of 57725

That all works surprising quickly (less than a minute), but what am I
misunderstanding or missing?

Regards,
Peter T

 

[joeu2004]

Ah, OK, so I had a go, and came up with 57725 6-number
cominations. Obviously that's not right but FWIW this is
what I did - [....]
That all works surprising quickly (less than a minute),
but what am I misunderstanding or missing?

I have no idea. I don't understand what you are trying to achieve; that is,
which problem you are working on, and with what constraints and goals. And
I don't understand your description of your algorithm. Obviously, uploading
the actual code to a file-sharing website would help. "A program is worth a
thousand words" ;-). But don't bother for my benefit alone. I think this
will be my last posting in this thread unless Martin has some questions.

First, after Googling "lottery wheel algorithm", it has become clear that
this has been a programming challenge for some time. There is some
interesting reading material out there. But I was unable to find useful
source code for any self-described "good" algorithms.

Second, after some further experimentation, it seems clear to me now that
Problem #1 is poorly specified. And I no longer see it as a useful problem
to solve. To elaborate just a bit....

My original deterministic algorithm found 2240 combinations of 6-of-36
numbers that contain unique 4-number sets (quads; aka 4-tuples). But to
what end?

I already demonstrated that it covers only 33,600 of the 58,905 combinations
of 4-of-36 numbers. So the 2240 combinations do not cover all possible ways
to match 4-of-6 drawn numbers.

Those 2240 combinations __are__ the minimum number of combinations needed to
cover all 36 numbers without repeating any quads. But only if we use that
particular deterministic algorithm. That is, only if we select 6-of-36
tuples in that order.

When I replace the deterministic algorithm with one that randomly selects
from all 1,947,792 combinations of 6-of-36 numbers (but only if every quad
of each combination is unique), I stumbled upon a set of 17(!) combinations
that cover all 36 numbers without repeating any quads.

And even that might not be the smallest set. I cannot prove one way or
another. But I note that with 17 6-tuples, each of the 36 numbers is used
2.833..33 times on average -- 1 to 6 times in practice. So theoretically,
there might be a solution with a smaller average; ergo, few 6-tuples.

Finally, with respect to problem #2 -- the wheeling problem -- I had
previously described a solution with 5456 combinations of 6-of-36 numbers
that cover all 58,905 combinations of 4-of-6 drawn numbers. That is, it
does cover all possible ways to match 4-of-6 drawn numbers.

(Recall that that includes some duplicate quads necessarily.)

But I had noted that I cannot prove whether or not that is an optimal
solution; that is, the fewest number of combinations.

I suspect it is not. But when I replaced the deterministic selection
algorithm with a random selection similar to the one described above, my
first attempt required a set of 5596 combinations of 6-of-36 numbers to
cover all 58,905 combinations of 4-of-6 drawn numbers. More combinations.

Nevertheless, that proves nothing. It is only one random trial.

Disclaimer.... I am not suggesting that random selection is the way to go.
I am merely using those random selection to stumble upon some alternate
solutions that, for me, offer some insight into the parameters of the
problem(s).

 

[Martin Brown]

I have tried to count this in the past, and I believe I never succeeded.

That is why I would like to see your 16,431 combinations.

My algorithm generated 2240; and I do not see any mistake (yet). I
posted a pointer to my uploaded file in another response.

My algorithm also generated 2240 for the base case with no repetitions
using a greedy take exactly 15 matches at a time only approach with a
starting seed value of 0x3f = 63 = 00111111b first time around.

But if I choose a random 6 bits are 1 starting seed instead I can get
slightly different values - best so far is from 0x333 = 1100110011b with
2244 hits followed by 0xAAA = 101010101010b with 2242 hits and the worst
so far 0x111111 with only 2233 hits.

I wonder if there is some neat way to generate manually by construction
a better set of test patterns instead of the entire 6/36 ~2M entries.
The closest I can think of is to use the structure of the problem 6C36
and treat it at a nested case of 3C6 6 bit long patterns placed in 2C12
positions and zero padded. (And also 6 bits all set in 6 positions)

3C6 = 6!/3!^2 = 20
2C12 = 12.11/2 = 76

My back of the envelope reasoning is that the 3C6 binary patterns can
have at most 2 matching bits in common and so the subset this generates
which contains 76.20.20 = 30400 elements all have less than or equal to
4 matching bits and might therefore stand a better chance of spanning
the space more efficiently than the brute force greedy method.

I haven't thought of a neat way to set the problem up that will allow an
efficient search of the very large space for a global optimum. Like you
I think the greedy method may not be optimal but cannot prove it.

So far my results are by trial and error.