
February 10th, 2011, 02:32 PM
#1
Lunch planner algorithm
My boss just asked me for a favor, he needs a lunch planner application. The idea is this; There is a guest list of N people, lets say 30. He wants to have Y lunches ( lets say 12 ), with no more than Z ( lets say 5 ) people at each lunch setting.
Now here is the trick, he wants to minimize the number of times the same people have lunch together.
I can think of a bruit force method to do this, create a big array and keep track of the number of times two people have met for lunch and then iterate over the array comparing values to find the minimum pairs. This may then take several sweeps because Person 1 and 2 might have only met once, but person 1 and 3 have met 8 times while person 2 and 3 have never met, etc...
I am sure this is one these exponential searches. However, it also occurs to me that there might simply be some pattern you can follow that will yield the best combo such that each person at each lunch has met the minimum number of times.
Any suggestions or help on this problem will greatly be appreciated.

February 10th, 2011, 10:01 PM
#2
Re: Lunch planner algorithm
Well, if this is just for inhouse interpersonal development, I recommend just going with random generation of groups. It's 'good enough' for your purposes.
If you're really dealing with only 30 people and lunches of 5 people then there are only 30 Choose 5 = 142,506 possible lunch groups. With 60 people and lunches of 5 each, there are 5 million possible groups. Both of these are not insane numbers; you could seriously just brute force them explicitly figuring out which group had met the least number of times every time you make a new lunch group assignment and choose that one as the next lunch group. It wouldn't be the fastest ever, but it would work within a few minutes to an hour.
Alternatively, I would go with a dynamic programming approach to get approximate solutions. To choose a new lunch group:
Consider a 'conflict' to exist when any member of a lunch group has had lunch with another member previously. Also, for a group, G, let countConflicts(G) return the number of conflicts in a group.
Code:
Randomly select Z people, calling them S (for solution)
Iterate:
Consider replacing EACH of the people in S with one of the (NZ) people not in S, call this T.
Figure out which T minimizes countConflicts(T)
If countConflicts(T) = countConflicts(S), you're done; otherwise:
Set S = T and iterate again.
Note that this will only generate approximately optimal solutions, so you might run the above algorithm 510 times per lunch assignment and then choose the best of those.
On each of the 'consider replacing...' steps you are only doing Z * (N Z) ~= Z*N comparisons which is much less than N choose Z and N^2. The tradeoff is that it's heuristic only.
Last edited by BioPhysEngr; February 10th, 2011 at 11:06 PM.
Reason: fixed some math.. d'oh!
Best Regards,
BioPhysEngr
http://blog.biophysengr.net

All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

February 10th, 2011, 10:06 PM
#3
Re: Lunch planner algorithm
I decided the pseudocode might possibly (?) be confusing (or not), so here is an alternate way to say the exact same thing:
Code:
Randomly select Z people, calling them S (for solution)
Iterate:
Set Tmin = S
Consider replacing EACH of the people in S with one of the people not in S, call this T.
If countConflicts(T) < countConflicts(Tmin)
Set Tmin = T
If Tmin = S, you're done; otherwise:
Set S = Tmin and iterate again.
Last edited by BioPhysEngr; February 10th, 2011 at 10:06 PM.
Reason: rmv extraneous code tag
Best Regards,
BioPhysEngr
http://blog.biophysengr.net

All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

February 11th, 2011, 08:52 AM
#4
Re: Lunch planner algorithm
That might work, but someone ( on another board) suggested to try a greedy algorithm search.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
