RE: Need a algorithm
- To: mathgroup at smc.vnet.net
- Subject: [mg33894] RE: [mg33857] Need a algorithm
- From: "DrBob" <majort at cox-internet.com>
- Date: Sun, 21 Apr 2002 06:14:36 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
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