Home 
Search 
Today's Posts 
#1




List all combinations of 6/36 with unique 4 numbers
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 
#2




Answer: List all combinations of 6/36 with unique 4 numbers
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 (136) without any repetition of the same combination. Here's how you can do it in Excel:
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.
__________________
I am not human. I am an Excel Wizard 
#3
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"Martin888" 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? "Martin888" 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? 
#4




Quote:
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 :) Quote:
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? Quote:
Please let me know if you need more info :) Thanks! 
#5




[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 
#6
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"Martin888" 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. "Martin888" 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". "Martin888" 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 selfexplanatory. Let me know if you have any questions or comments. 
#7




Quote:
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. 
#8
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
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.eternalseptember.org ClassicVB Users Regroup! comp.lang.basic.visual.misc microsoft.public.vb.general.discussion 
#9
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
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 "Martin888" 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  Martin888 
#10
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
I wrote:
"Martin888" 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 4number match", as the "wheelers" put it. I will be doublechecking 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: "Martin888" 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 4number match. With a full wheel, a minimum 4number 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 4number 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. 
#11
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
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 fullwheel conditional probability is correct, I have my doubts about the formula for the abbreviatedwheel conditional probability. I need to give that more thought. 
#12
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"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 filesharing website and post the "shared", "public" or "viewonly" link (aka URL; http://...) in a response here. The following is a list of some free filesharing 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 
#13
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"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 fullwheel conditional probability is correct, I have my doubts about the formula for the abbreviatedwheel conditional probability. I need to give that more thought. =COMBIN(36,6) That returns 1947792 which is indeed the number of 6number 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 
#14
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"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. 
#15
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"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. 
#16
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"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 filesharing 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 6number 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 
#17




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...ddsofwinning 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 
#18
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"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 much 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. 
#19
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"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 much 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 
#20
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
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.eternalseptember.org ClassicVB Users Regroup! comp.lang.basic.visual.misc microsoft.public.vb.general.discussion 
#21
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"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 much 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 
#22
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"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 doublecheck. 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 4number 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.) 
#23
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"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 4number 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 
#24
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"Martin888" 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 4number 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. "Martin888" 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 powerballtype 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. 
#25
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
PS.... I wrote:
"Martin888" 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. 
#26
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 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 6number cominations. Obviously that's not right but FWIW this is what I did  Make the 58905 4number 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 6number combinations, and make 3 equivalent 'long' numbers with each, eg for 1,2,3,4,5,6 make 1020304 : 2030405 : 3040506 lookup 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 159k 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 
#27
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
"Peter T" wrote in message
... Ah, OK, so I had a go, and came up with 57725 6number 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 filesharing 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 selfdescribed "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 6of36 numbers that contain unique 4number sets (quads; aka 4tuples). But to what end? I already demonstrated that it covers only 33,600 of the 58,905 combinations of 4of36 numbers. So the 2240 combinations do not cover all possible ways to match 4of6 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 6of36 tuples in that order. When I replace the deterministic algorithm with one that randomly selects from all 1,947,792 combinations of 6of36 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 6tuples, 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 6tuples. Finally, with respect to problem #2  the wheeling problem  I had previously described a solution with 5456 combinations of 6of36 numbers that cover all 58,905 combinations of 4of6 drawn numbers. That is, it does cover all possible ways to match 4of6 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 6of36 numbers to cover all 58,905 combinations of 4of6 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). 
#28
Posted to microsoft.public.excel.programming




List all combinations of 6/36 with unique 4 numbers
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 
Reply 
Thread Tools  Search this Thread 
Display Modes  


Similar Threads  
Thread  Forum  
sum up combinations of numbers from list to get specific total  Excel Discussion (Misc queries)  
Unique combinations of records in a list  Excel Programming  
Unique random numbers from list  Excel Discussion (Misc queries)  
List of unique texts and numbers  Excel Worksheet Functions  
how to extract unique numbers once from a list of repeated numbers?  Excel Discussion (Misc queries) 