RE: RE: Need a algorithm

*To*: mathgroup at smc.vnet.net*Subject*: [mg33907] RE: [mg33894] RE: [mg33857] Need a algorithm*From*: "DrBob" <majort at cox-internet.com>*Date*: Mon, 22 Apr 2002 00:57:46 -0400 (EDT)*Reply-to*: <drbob at bigfoot.com>*Sender*: owner-wri-mathgroup at wolfram.com

I suspected this algorithm would not always give optimal answers, and I was right. It occurred to me that choosing the First draw with minimal (worst) match with already bought tickets would prejudice the algorithm in an unfortunate direction, so I replaced First with a random draw. (Note that \[Intersection] represents the intersection symbol. Just copy the text into a notebook.) ClearAll[minMatch,buyNext,pickOne] pickOne[a_List]:=a[[Random[Integer,{1,Length[a]}]]]; buyNext:=Module[{nxt}, nxt=Flatten[s[[pickOne[Position[t,Min[t]]]]]]; t=MapIndexed[Max[#1,Length[s[[First[#2]]]\[Intersection]nxt]]&,t]; minMatch=Min[t]; AppendTo[tickets,nxt] ] s=KSubsets[q,7]; pickTickets[k_]:=( tickets={}; minMatch=0; t=0&/@s; While[minMatch<k,buyNext]; tickets//Length ) This code doesn't always give the same answer because of the randomness involved. Better answers than before were achieved on just about every trial, and it runs faster as well (because it stops earlier). In ten trials for k=5 to k=6, I had the following results (numbers of tickets): {{10,10,10,9,8,10,10,9,9,10},{57,53,57,58,59,60,59,57,55,62}} Thus 8 tickets are enough for k=5 and 53 for k=6, compared to the earlier answers of 10 and 63. More trials might find even better answers, so I ran it 100 times and chose the smallest number of tickets found: In[156]:= Timing[ Min/@Table[pickTickets[n],{n,5,6},{i,1,100}] ] Out[156]= {104.063 Second,{7,53}} 7 tickets suffice for k=5, and 53 tickets for k=6. But 500 iterations gave an even better answer for k=6: In[157]:= Timing[ Min/@Table[pickTickets[n],{n,5,6},{i,1,500}] ] Out[157]= {514.578 Second,{7,52}} Unfortunately, another trial of 500 iterations gave the answers 8 and 52. If this many iterations are required to get an answer that may still be larger than optimal, exhaustive search may be indicated instead of the heuristic search I've used. However, there are MANY possibilities when looking at 6 tickets, for instance. This is probably a straight-forward problem in coding theory, by the way. Bobby Treat -----Original Message----- From: DrBob [mailto:majort at cox-internet.com] To: mathgroup at smc.vnet.net Subject: [mg33907] [mg33894] RE: [mg33857] Need a algorithm Here's code that finds a good (but perhaps not optimal) solution (again, if I've understood the problem statement). It's a "greedy" algorithm that selects tickets in turn. It looks at all possible lottery draws and selects one with minimal match with tickets already bought; that draw is the next ticket bought. q={8,11,13,14,16,22,23,28,31,32,34,35}; s=KSubsets[q,7]; minMatch:=Module[{t,m}, t=Outer[Intersection,s,tickets,1]; m=Min[Max[Length/@#]&/@t] ] maxMatch[s_List]:=Max[Length/@(#\[Intersection]s&/@tick)] buyNext:=Module[{t}, t=maxMatch/@s; Flatten[s[[First[Position[t,Min[t]]]]]] ] k=5; tickets={Take[q,7]} While[minMatch<k, AppendTo[tickets,buyNext] ]; tickets For k=2, the result is {{8,11,13,14,16,22,23}}. For k=3 and 4, the result is {{8,11,13,14,16,22,23},{8,11,28,31,32,34,35}} For k=5, the result is 10 tickets: {{8,11,13,14,16,22,23},{8,11,28,31,32,34,35},{8,13,14,16,28,31,32}, {8,13,14,22,28,34,35},{8,13,16,23,31,34,35},{8,14,22,23,31,32,34}, {8,16,22,23,28,32,35},{11,13,14,16,32,34,35},{11,13,14,23,28,31,34}, {11,13,16,22,28,31,35}} For k=6, the result is 63 tickets. On my 2.2 GHz Pentium 4, this code took 28 seconds for k=6, but less than one second for k=5. A much more efficient code is: ClearAll[maxMatch,minMatch,buyNext] maxMatch[s_List]:=maxMatch[s]=Max[Length/@(#\[Intersection]s&/@tickets)] buyNext:=Module[{nxt}, nxt=Flatten[s[[First[Position[t,Min[t]]]]]]; t=MapIndexed[Max[#1,Length[First[s[[#2]]]\[Intersection]nxt]]&,t]; minMatch=Min[t]; AppendTo[tickets,nxt] ] tickets={}; minMatch=0; s=KSubsets[q,7]; t=0&/@s; k=6; Timing[ While[minMatch<k, buyNext ]; ] tickets//Dimensions This code solved for k=6 in 1 second and k=7 in 13 seconds. It prevails because unnecessary Outer products are eliminated, and intersections of subsets of q with tickets already bought are eliminated. Bobby Treat