Hello!

I've been looking at this all over the internet, and either I'm the first one that looks for this or I can't word it properly... I can't find anything.

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. There should be around 320 combinations.

For example these would be valid combinations:

1 2 3 4 5 6
1 2 3 7 8 9
1 2 4 10 11 12

These wouldn't be valid:

1 2 3 4 5 6

1 2 3 4 5 7

2 3 4 6 10 11

because "1 2 3 4" and "2 3 4 6" are appearing twice.

I hope someone will be kind enough to point me to the right direction. Please let me know if my explanation isn't clear.

Thanks a bunch!

Martin

Hi Martin!

I understand what you're looking for. You want to generate all possible combinations of 4 unique numbers from a set of 6 numbers (1-36) without any repetition of the same combination. Here's how you can do it in Excel:

1. Create a column for each of the 6 numbers (let's say A, B, C, D, E, F).
2. In the next column, use the formula =COMBIN(6,4) to calculate the total number of possible combinations of 4 numbers from 6.
3. In the next column, use the formula =RAND() to generate a random number for each row.
4. Sort the table by the random number column (ascending or descending, it doesn't matter).
5. In the next column, use the formula =A2&B2&C2&D2 to concatenate the 4 numbers in each row into a single cell.
6. In the next column, use the formula =IF(COUNTIF($E$2:E2,E2)=1,"Valid","Duplicate") to check if the combination in each row is valid (unique) or a duplicate.
7. Filter the table by the "Valid" column to show only the valid combinations.

That's it! You should now have a list of all possible combinations of 4 unique numbers from 6 without any repetition of the same combination. Let me know if you have any questions or if anything is unclear.

"Martin-888" wrote:
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.

I would like to help.

But first, let's agree to ignore those whose only comment is to pontificate
about how foolish playing the lottery is. Yes, yes, yes; just like all
gambling. But it presents some very interesting, if not fun, mathematical
problems. After all, it was the analysis of games of chance that gave rise
to probability theory in the first place.

So I am not judging your motivations. "Frankly, my dear, I don't give a
damn!" :-)

But I am curious, because this question has come up before.

So please explain the context of this question.

For example, is it a class assignment?

Or is it part of a lottery strategy? If so, can you explain the strategy,
or can you point to a (free) website that does?


"Martin-888" wrote:
There should be around 320 combinations.
For example these would be valid combinations:
1 2 3 4 5 6
1 2 3 7 8 9
1 2 4 10 11 12
These wouldn't be valid:
1 2 3 4 5 6
1 2 3 4 5 7
2 3 4 6 10 11
because "1 2 3 4" and "2 3 4 6" are appearing twice.

Based on this example, I think a better description of your objective is:
all combinations of 6 out of 36 numbers with a unique set of 4 numbers.

It has nothing to do with "winning" 4 out of 6. To me, that means:
matching 4 out of 6 compared to some drawing of 6 numbers. That's a very
different problem; an easier problem to solve, IMHO.

Anyway, what makes you think there are only "around 320" such combinations?

I believe the correct count is 2240.

At the risk of reinventing the wheel (I cannot find my comments in the
previous discussion), I implemented an algorithm that counts and generates
all of the qualified combinations by exhaustively generating all
COMBIN(36,6) combinations (1,947,792) and keeping track of the ones with
unique sets of 4 numbers. It only takes about 1 second on my computer.
(YMMV.)

I will share that implementation with you after you answer my questions
above.

In the meantime, I am still improving the implmentation so it is easier for
public consumption. I would also like to see if there is a better
algorithm. And I am still strugging to derive a computational method for
counting the number of combinations.

In any case, be advised that this cannot be done with Excel alone. Instead,
it requires a VBA subroutine (macro). Is that acceptable?

First of all, thank you for being interested in my question :)

It is part of a lottery strategy, but it does imply buying all the 320 combinations (which I'll explain why I think there is only 320 combinations later), therefore guaranteeing at least one win of the 4 out of 6 prize. Also I just want to point out that English isn't my native language, sometimes I run out of word to properly explain my thought :)

I'm not very good in math, but since there is 1 chance out of 320, it made me believe that there was many groups of 320 combinations. Having Excel taking out all of the matching combinations would answer that question.

Just to make sure that I'm properly understood, I want to clarify a point.

In my 4 out of 6 unique combinations, the 4 out of 6 has to be completely unique:

If you take 1,2,3,4,5,6 as my starting combination, the other combinations will not be able to have the following inside of them:

1,2,3,4
2,3,4,5
3,4,5,6
1,3,4,5
1,4,5,6
2,4,5,6
1,2,4,5
1,2,5,6
1,3,4,6
1,3,5,6
1,4,5,6

So for the script to work properly, the next logical combination would be 1,2,3,7,8,9 since 1,2,3,4,5,7 wouldn't be an acceptable one. Also, starting with the first combination being 2,3,4,5,6,7 then this creates a different list of combinations, with different exclusions. I hope this makes more sense?

VBA script is perfect, I didn't think that Excel alone would be able to create this either. Is this how you first understood my question or my clarification changes it? Also, your algorithm that creates all the combinations within 1 second is impressive, all the ones I found online takes nearly 1 hour to complete and I have a Core i7.

Please let me know if you need more info :)

Thanks!

[Hello Martin,

i think that right answer is 58 905 rows.

Try these macros. I suppose that you know about macros, so
that you can try these ones.

First takes about 10 mins and second taken about 2 minutes.

best regards

"Martin-888" wrote:
It is part of a lottery strategy, but it does imply buying
all the 320 combinations [...], therefore guaranteeing at
least one win of the 4 out of 6 prize.

Sounds like a scam.

Please provide a URL (http://...) for the website that describes the
strategy or offers the product.

Also, please provide a URL (http://...) for the particular lottery.


"Martin-888" wrote:
I'm not very good in math, but since there is 1 chance
out of 320, it made me believe that there was many groups
of 320 combinations.

No. For example, there are 6525 ways (tickets) of matching exactly 4 out of
6 numbers drawn. That translates into about a 1 in 298.5 chance of matching
exactly 4, since there are 1,947,792 possible drawings (tickets) of 6 out of
36 numbers.

I still do not understand where 320 comes from. That is why I would like
the URLs that I requested above. They probably don't explain the math
directly. But they might have information that I can use to intuit the
computation.

For now, I stand by my finding that you would have to buy 2240 tickets in
order to be sure to match at least 4 of 6.

Of course, that makes sense to do only if the payout for matching exactly 4
is more than $2240, assuming $1 per ticket. (And of course, by "$", I mean
whatever your currency is.)

I suspect you will find that the payout is much smaller. Otherwise,
everyone would be doing this.

"If it sounds too good to be true, it usually is".


"Martin-888" wrote:
In my 4 out of 6 unique combinations, the 4 out of 6 has
to be completely unique
[....]
Is this how you first understood my question

Yes. You can download the file "uniq 4 from 6 of 36.xls" from
https://www.box.com/s/2a361ad6de78e8f4865e.

Columns A and B are somewhat configurable by changing A1, A2 and A3.
However, the table starting at A11 might need to be adjusted manually.

The macro that generates the results in columns D through I is hardwired for
the particular parameters that you mentioned, namely: drawing 6 of 36
numbers, and generating all combinations with unique sets of 4 numbers.

I hardwired the numbers in order to ensure the best performance.

The worksheet and macro might not be very self-explanatory. Let me know if
you have any questions or comments.

Hello!

Thank you for the VBA script, unfortunately that gives me 4 numbers combinations, which doesn't work for what I need; I need 6 numbers combination with a unique 4 numbers combinations inside of it. While this script would give me the first 4 numbers, it wouldn't detect a match in the rest of the combinations, when the extra 2 numbers are added. For example:

If the script gives me this:

1,2,3,4
1,2,3,5
1,2,3,6
1,2,3,7

I need to add the extra two digits, which will then create duplicate unique 4 numbers within the combination:

1,2,3,4,5,6
1,2,3,5,6,7

Here you have 1,2,3,5 & 1,2,3,6 & 1,2,5,6 & 1,3,5,6 & 2,3,5,6 that matches in both combinations.

I believe what you are looking for is 'lotto wheeling' algorithms. If
you google that you'll find there's many samples of popular wheeling
combos for 6 number draws that will claim to result in 3/4/5/6 out of
<numbers drawn odds of winning *IF* the numbers drawn happen to be in
your wheel. There are also what is called 'abbreviated' wheeling combos
which do not include all possible combos of candidate numbers, but
these are based on popular combos with the same win ratio as full
wheels. In any case you need to provide the required 'candidate'
numbers for the chosen wheel. For example...

One popular (abbreviated) wheeling combo generates 42 tickets with a
5 out of 6 odds of winning based on using only 16 candidate numbers.
The full wheel would generate all possible combinations of those 16
candidate numbers.

...where the cost/return ratio of this could be prohibitive at best if
you did not choose the right 16 candidate numbers!

Lotteries are 'random' gaming that do not have any 'mystical' results
attached<IMO, and so there are no 'guaranteed' ways to win other than
playing a full wheel of every possible ticket combo for the numbers
used (ie: 6/39, 6/49, 7/49...)!!!

--
Garry

Free usenet access at http://www.eternal-september.org
ClassicVB Users Regroup!
comp.lang.basic.visual.misc
microsoft.public.vb.general.discussion

I knocked something up to get a feel, pretty crude and slow but it churned
out 1,947,792 combinations of 6 numbers of which 16,431 fitted your '4 out
of 6' criteria. IOW would need to buy 16k tickets. Before spending time
trying to figure out what I might have misunderstood or why the routine
might be wrong, please explain why you are say "There should be around 320
combinations."

Regards,
Peter T



"Martin-888" wrote in message
...

Hello!

I've been looking at this all over the internet, and either I'm the
first one that looks for this or I can't word it properly... I can't
find anything.

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. There should be around
320 combinations.

For example these would be valid combinations:

1 2 3 4 5 6
1 2 3 7 8 9
1 2 4 10 11 12

These wouldn't be valid:

1 2 3 4 5 6

1 2 3 4 5 7

2 3 4 6 10 11

because "1 2 3 4" and "2 3 4 6" are appearing twice.

I hope someone will be kind enough to point me to the right direction.
Please let me know if my explanation isn't clear.

Thanks a bunch!

Martin




--
Martin-888

I wrote:
"Martin-888" wrote:
It is part of a lottery strategy, but it does imply buying
all the 320 combinations [...], therefore guaranteeing at
least one win of the 4 out of 6 prize.

Sounds like a scam.

Please provide a URL (http://...) for the website that describes
the strategy or offers the product.

Aha! I believe you are talking about what is called "lottery wheels" and
"lottery wheeling" in English.

But I believe you might have misunderstood some details. And quite
understandably so, especially if you are reading English descriptions, and
English is not your native language, as you indicated. I found it difficult
to understand some of the details, and English __is__ my native language
:-). I finally "got it" after reading several descriptions and examples.


I wrote:
For now, I stand by my finding that you would have to buy 2240
tickets in order to be sure to match at least 4 of 6.

I am even more confident now that I correctly "wheeled" the full set of 36
numbers to guarantee "a minimum 4-number match", as the "wheelers" put it.

I will be double-checking my algorithm later, just to be sure I don't have a
defect.

Nevertheless, I suspect that is not exactly what you wanted, at least not
according to one detail that you posted.


I wrote:
"Martin-888" wrote:
I'm not very good in math, but since there is 1 chance
out of 320, it made me believe that there was many groups
of 320 combinations.
[....]
I still do not understand where 320 comes from.

I believe I do, now. But I wonder if you really meant to write 1 chance in
389, 325, or 315, not 320.

There are two common flavors of lottery wheeling: full wheel and
abbreviated wheel. (There are other flavors, as well.)

With a full wheel, you typically choose a subset of the 36 numbers, say 18
numbers. Then we generate __all__ combinations of 6 of the __18__ numbers,
not 36, with unique sets of 4. That would be a total of 42 combinations in
this case.

With an abbreviated wheel, again you choose a subset of the 36 numbers, say
18 numbers. Then we generate a __subset__ of the combinations 6 of the
__18__ numbers with unique set of 4. That would be fewer than 42
combinations in this case. (See below for how we define the subset of
qualified combinations.)

The key difference is the condition under which the wheel "guarantees" a
minimum 4-number match.

With a full wheel, a minimum 4-number match is "guaranteed" as long as
__all_6__ of the drawn numbers (by the lottery) are in your subset of 18
numbers.

With an abbreviate wheel, a minimum 4-number match is "guaranteed" as long
as, for example, at least __4__ of the 6 drawn numbers are in your subset of
18 numbers.

At issue is the word "guaranteed". It is really a __conditional__
guarantee.

Given the condition for full wheels ("all 6 of the drawn numbers are in your
subset"), the probability that the condition is met is COMBIN(18,6) /
COMBIN(36,6) for a subset is 18 numbers.

Similarly, for abbreviated wheels, the probability that the condition ("at
least 4 of the drawn numbers are in your subset") is met is COMBIN(18,4) /
COMBIN(36/6).

This is where the "1 chance in 320" comes from: ostensibly, COMBIN(k,6) /
COMBIN(36,6) is 1/320 for some subset of k numbers.

However, I am unable to find any k for which the conditional probability is
exactly 1/320.

It would be 1/389 (1 chance in 389) for a full wheel with a subset of 15
numbers.

It would be 1/325 for an abbreviated wheel with a subset of 21 numbers and
the condition that at least 4 of the 6 drawn numbers are in the subset.

And it would be 1/315 for an abbreviated wheel with a subset of 17 numbers
and the condition that at least 5 of the 6 drawn numbers are in the subset.

Does any of that sound familiar -- closer to the facts in your circumstance?


I wrote:
Of course, that makes sense to do only if the payout
for matching exactly 4 is more than $2240, assuming $1
per ticket.

I neglected to also take into consideration other possible lesser matches
with some of the other combinations. That is too complicated to explain
further. I hope you can imagine what I mean.

PS: It might useful if I modify my algorithm to handle any full and
abbreviated wheel characteristics. Something for the future.

Errata.... I wrote:
Given the condition for full wheels ("all 6 of the drawn numbers are in
your subset"), the probability that the condition is met is COMBIN(18,6) /
COMBIN(36,6) for a subset is 18 numbers.

Similarly, for abbreviated wheels, the probability that the condition ("at
least 4 of the drawn numbers are in your subset") is met is COMBIN(18,4) /
COMBIN(36/6).

While I believe the full-wheel conditional probability is correct, I have my
doubts about the formula for the abbreviated-wheel conditional probability.
I need to give that more thought.

"Peter T" wrote:
I knocked something up to get a feel, pretty crude
and slow but it churned out 1,947,792 combinations
of 6 numbers of which 16,431 fitted your '4 out of 6' criteria.

I would like to understand why you and I got very different results.

Please upload your results -- the 16,431 combinations -- to a file-sharing
website and post the "shared", "public" or "view-only" link (aka URL;
http://...) in a response here. The following is a list of some free
file-sharing websites; or use your own.

Box.Net: http://www.box.net/files
Windows Live Skydrive: http://skydrive.live.com
MediaFi http://www.mediafire.com
FileFactory: http://www.filefactory.com
FileSavr: http://www.filesavr.com
FileDropper: http://www.filedropper.com
RapidSha http://www.rapidshare.com

"joeu2004" wrote in message
...
Errata.... I wrote:
Given the condition for full wheels ("all 6 of the drawn numbers are in
your subset"), the probability that the condition is met is COMBIN(18,6)
/ COMBIN(36,6) for a subset is 18 numbers.

Similarly, for abbreviated wheels, the probability that the condition
("at least 4 of the drawn numbers are in your subset") is met is
COMBIN(18,4) / COMBIN(36/6).

While I believe the full-wheel conditional probability is correct, I have
my doubts about the formula for the abbreviated-wheel conditional
probability. I need to give that more thought.

=COMBIN(36,6)

That returns 1947792 which is indeed the number of 6-number combinations my
routine churns out before 'filtering'. Now if you can derive some formula
that returns 16431 for the filtered '4 out of 6' that would validate my
routine!

Regards,
Peter T

"GS" wrote:
One popular (abbreviated) wheeling combo generates 42
tickets with a 5 out of 6 odds of winning based on using
only 16 candidate numbers.

Please post a pointer to this website. I would like to understand those
odds ("5 out of 6") better.

Or do you mean: 5 out of 6 odds of matching at least some number (4?), but
__only_if__ at least some number (4?) of the drawn numbers are in the subset
of 16 numbers?

In other words, the real probability of "winning" is 5/6 times some
conditional probability (TBD)?

Even so, I would be interested in looking at the website.

"Peter T" wrote:
Now if you can derive some formula that returns 16431
for the filtered '4 out of 6' that would validate my routine!

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.

"joeu2004" wrote in message
...
"Peter T" wrote:
I knocked something up to get a feel, pretty crude
and slow but it churned out 1,947,792 combinations
of 6 numbers of which 16,431 fitted your '4 out of 6' criteria.

I would like to understand why you and I got very different results.

Please upload your results -- the 16,431 combinations -- to a file-sharing
website

16,431, after spotting a small error now only 16,430

It's small enough to post here, but watch for word wrap -

Option Explicit
Sub test6()
Dim i As Long, j As Long
Dim s As String
Dim arrCombs() As Long

Range("a:a").Clear

Combs4from6 arrCombs, 36

For i = 1 To UBound(arrCombs, 2)
s = arrCombs(1, i)
For j = 2 To 6
s = s & " " & arrCombs(j, i)
Next
Cells(i, 1) = s
Next

End Sub

Function Combs4from6(bigArr, mx As Long) As Long
Dim a1 As Long, a2 As Long, a3 As Long, a4 As Long, a5 As Long, a6 As Long
Dim i As Long, j As Long
Dim r As Long, x As Long

ReDim arr(1 To 6) As Long
ReDim bigArr(1 To 6, 1 To 1000) As Long

For a1 = mx - (mx - 6) + 1 To mx
arr(1) = arr(1) + 1
arr(2) = arr(1)
For a2 = a1 - 1 To mx
arr(2) = arr(2) + 1
arr(3) = arr(2)
For a3 = a2 To mx
arr(3) = arr(3) + 1
arr(4) = arr(3)
For a4 = a3 To mx
arr(4) = arr(4) + 1
arr(5) = arr(4)
For a5 = a4 To mx
arr(5) = arr(5) + 1
arr(6) = arr(5)
For a6 = a5 To mx
arr(6) = arr(6) + 1
r = r + 1
filterComb bigArr, arr, x
Next
Next
Next
Next
Next
Next

' the last one
For i = 1 To 6
arr(i) = mx - 6 + i
Next
filterComb bigArr, arr, x

ReDim Preserve bigArr(1 To 6, 1 To x)

Combs4from6 = x
End Function
Function filterComb(bigArr, arr() As Long, x As Long) As Boolean
Dim b As Boolean
Dim i As Long, j As Long, k As Long
Dim f As Long

On Error GoTo errH

If x < 1 Then
x = x + 1
For i = 1 To 6
bigArr(i, 1) = arr(i)
Next
filterComb = True
Else

For i = 1 To x
f = 0

For j = 1 To 6
For k = 1 To 6
If bigArr(j, x) = arr(k) Then
b = True
Exit For
End If
Next

If b Then
f = f + 1
b = False
If f = 4 Then
' already found 4 dups, no point to look for more
Exit Function
End If
End If

If j - f 2 Then
' can't be 4 dups in this array so skip to the next
Exit For
End If

Next
Next

x = x + 1
For i = 1 To 6
999 bigArr(i, x) = arr(i)
Next
filterComb = True
End If

Exit Function
errH:
If Err.Number = 9 And Erl = 999 Then
'need to resize the array
ReDim Preserve bigArr(1 To 6, 1 To UBound(bigArr, 2) + 1000)
Resume
End If

End Function

It works like this
- Combs4from6 makes all the 6-number combinations, each temporarily to a 6
number array.
- filterComb compares the array looking for 4 duplicate numbers in all
previously retained arrays. If 4 dups are not found the array of 6 is added
to the main array

Combs4from6 is I think highly efficient and well optimzed. filterComb is
'efficient' but the entire approach isn't. If filterComb is commented in
Combs4from6 1.9m combinations are produced in barely a tad. However the
filter approach means take a coffee or two. Probably a different approach
would speed things up considerably. In particular, look into only making
correct combinations (rather than all 1.9m) in the first place and avoid the
need to filter; it's one of those "'get your head round it' sort of things!

I have NOT checked results, so until otherwise confirmed do not assume this
all works correctly!

Regards,
Peter T

Thank you everyone for looking into this, I think joeu is right, it is 2240 tickets that I would need to make sure that I win 4 out of 6 and not 320. I'm not very good at math, I will not comment all the technical details that you guys provided, as I don't understand them properly :)

Here is the link of the game:

http://lotoquebec.com/loteries/nav/e...dds-of-winning

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

I wasn't looking for a way to win more money that I would be paying for the tickets everytime, but more looking for a cheaper way of buying many tickets, increasing the chance of winning the 6/6 prize.

Thanks everyone for your help on this, especially joeu :)

Martin

"Peter T" wrote:
"joeu2004" wrote in message
"Peter T" wrote:
I knocked something up to get a feel, pretty crude
and slow but it churned out 1,947,792 combinations
of 6 numbers of which 16,431 fitted your '4 out of 6' criteria.

I would like to understand why you and I got very different results.
[....]
16,431, after spotting a small error now only 16,430 It's small enough to
post here

Well, that implementation does not seem to work at all.

Of the 16,430 combinations, only 153 fit Martin's requirement, namely:
every quad subset of the 6 numbers in each combination is unique (there are
15 such quad subsets). That is, they do not appear together in any other
combination.

If you are intereted, see "peterT combo.xls" at
https://www.box.com/s/409aee79b7b3949970f1. See the explanation in the
worksheet "README FIRST".

For example, in the "data" worksheet, combination/row #12 shows:

A C:H I J:O
1 2 4 5 6 7 1 2 4 5 6 7 #1 1 2 3 4 5 6

Note that 1 2 4 5 in C:H appeared first in row #1, shown in J:O for
convenience. I believe that violates Martin's requirements.

There really is no need for me to try to identify the flaw(s) in your
implementation. I had already pointed to my implementation, which seems to
truly work (and it is m-u-c-h faster). It produces 2240 combinations with
unique quad subsets.

If you are interested, see "uniq 4 from 6 of 36.xls" at
https://www.box.com/s/2a361ad6de78e8f4865e.

"joeu2004" wrote in message
...

There really is no need for me to try to identify the flaw(s) in your
implementation. I had already pointed to my implementation, which seems
to truly work (and it is m-u-c-h faster). It produces 2240 combinations
with unique quad subsets.
If you are interested, see "uniq 4 from 6 of 36.xls" at
https://www.box.com/s/2a361ad6de78e8f4865e.

Yeah there was a silly typo in mine,
in filterComb change
If bigArr(j, x) = arr(k) Then
to
If bigArr(j, i) = arr(k) Then

and guess what - it also returns 2240 combinations !

With that change although probably now correct it's even slower, I'll look
at yours tomorrow.

That said, presumably the task is a one off so I suppose speed is not
critical.

Regards,
Peter T

joeu2004 has brought this to us :
"GS" wrote:
One popular (abbreviated) wheeling combo generates 42
tickets with a 5 out of 6 odds of winning based on using
only 16 candidate numbers.

Please post a pointer to this website. I would like to understand those odds
("5 out of 6") better.

Or do you mean: 5 out of 6 odds of matching at least some number (4?), but
__only_if__ at least some number (4?) of the drawn numbers are in the subset
of 16 numbers?

In other words, the real probability of "winning" is 5/6 times some
conditional probability (TBD)?

Even so, I would be interested in looking at the website.

I don't have a link to any particular website per se. I just googled
"lottery wheeling" and got lots of hits!

--
Garry

Free usenet access at http://www.eternal-september.org
ClassicVB Users Regroup!
comp.lang.basic.visual.misc
microsoft.public.vb.general.discussion

"joeu2004" wrote in message
...

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, but no worries, as I've already posted there
was a single letter typo in my code, it now produces same results as yours
(and in same order).

There really is no need for me to try to identify the flaw(s) in your
implementation. I had already pointed to my implementation, which seems
to truly work (and it is m-u-c-h faster). It produces 2240 combinations
with unique quad subsets.

Just to recap, as I mentioned I knocked something up very quickly just to
get a feel, not even sure I understood the objective yet alone if mine was
correct. You asked me to post it which I did. You didn't appear to be
entirely confirdent about yours either at the time.

Anyway, indeed yours is indeed very much faster, and very elegant too.
Actally the main aspects of both out codes are very similar (albeit not at
first glance). However but my filter approach is, not wrong but, poorly
conceived. Maybe a fresh look would have brought that in line with yours
too.

regards,
Peter T

"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.)

"joeu2004" wrote in message
...

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

"Martin-888" wrote:
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.


"Martin-888" wrote:
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.

PS.... I wrote:
"Martin-888" wrote:
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.

"joeu2004" wrote in message
...

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

"Peter T" wrote in message
...
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).

On 14/07/2012 18:22, joeu2004 wrote:
"Peter T" wrote:
Now if you can derive some formula that returns 16431
for the filtered '4 out of 6' that would validate my routine!

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.

--
Regards,
Martin Brown