"Peter T" wrote:
If you are intereted, see "peterT combo.xls" at
https://www.box.com/s/409aee79b7b3949970f1. See the
explanation in the worksheet "README FIRST".
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.
"Peter T" wrote:
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.)