Lunch planner algorithm

[DeepT]

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.

[BioPhysEngr]

Well, if this is just for in-house 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.

Randomly select Z people, calling them S (for solution)
Iterate:
   Consider replacing EACH of the people in S with one of the (N-Z) 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 5-10 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.

[BioPhysEngr]

I decided the pseudocode might possibly (?) be confusing (or not), so here is an alternate way to say the exact same thing:

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.

[DeepT]

That might work, but someone ( on another board) suggested to try a greedy algorithm search.