Lunch planner algorithm
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Lunch planner algorithm

  1. #1
    Join Date
    Sep 2004
    Posts
    1,361

    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.

  2. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,006

    Re: Lunch planner algorithm

    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.

    Code:
    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.
    Last edited by BioPhysEngr; February 10th, 2011 at 10: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.

  3. #3
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,006

    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 09: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.

  4. #4
    Join Date
    Sep 2004
    Posts
    1,361

    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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center