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)
• 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)]

t=maxMatch/@s;

Flatten[s[[First[Position[t,Min[t]]]]]]

]

k=5;

tickets={Take[q,7]}

While[minMatch<k,

];

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:

maxMatch[s_List]:=maxMatch[s]=Max[Length/@(#\[Intersection]s&/@tickets)]

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,

];

]

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

```

• Prev by Date: RE: How Do You Reduce Multiple Elements in a List?
• Next by Date: RE: Need a algorithm
• Previous by thread: Need a algorithm
• Next by thread: RE: Need a algorithm