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.

[Zylon]

Z = N / Y

Next!

[jellyfish]

I think brute force is the way to go here.

You need to know how many times each guest has seen each other guest.
So hold an NxN matrix of counts.

To get the party started, add the person who has been to the least parties. Alternatively, you can add the person who has another person he has seen less than any other person.

To add a guest to an existing party, look at the guests currently in the party and see how many times each non participating person has seen all the in party guests in total. Add the person with the minimum number of total views.

Repeat until full and then start a new party.

I can not guarantee this will optimize some preexisting party history (since it is greedy. But it still might). But it will optimize a new party schedule.

For example, 4 guests (misters 0,1,2,3), 20 parties, 3 guests per party.
[[0, 1, 2], [3, 0, 1], [2, 3, 0], [1, 2, 3], [0, 1, 2], [3, 0, 1], [2, 3, 0], [1, 2, 3], [0, 1, 2], [3, 0, 1], [2, 3, 0], [1, 2, 3], [0, 1, 2], [3, 0, 1], [2, 3, 0], [1, 2, 3], [0, 1, 2], [3, 0, 1], [2, 3, 0], [1, 2, 3]]

Each guests has been to 15 out of the 20 parties and each guest saw each other guest exactly 10 times.

Python code available on request.

I am drunk. Hopefully I haven't made any glaring errors.

[James Gutierrez]

I think brute force is the way to go here.

Yeah, this is good advice in general. Brute force > clever until proven otherwise.

[nKoan]

Especially with 30 entries. Your computer can brute force that in milliseconds.

[jellyfish]

And the running time complexity is linear and not exponential.

[DeepT]

Ok, ill try that Jellyfish. Thanks. Although if I think about it, I am certain it is not linear or maybe I am misunderstanding.

Pick guest 1 find the next guest who has seen guest 1 the least. Lets say that is guest 2. Now I need another guest and he needs to be compared to 1 and 2 x N pool of guests. The 4th guest needs to be compared to the first 3, etc.. However the pool is small so it should work out.

Oh, if you wrote this in python, sure, post it. I am writing it in c#.

[jellyfish]

Each time we need to add a guest to an existing party, we need to sum all rows of the counts matrix, but only for columns representing guests who are currently in the party. This new vector gives the total number of views each potential guests has seen all in party guests combined. Then we iterate over this new sum vector and take the minimum.

Creating the combined sum vector = i*n operations where i = number of guests in current party and n = total number of guests.

Since i is less than n we replace i with n and the running time is less than n^2.

Iterating over this vector to find the minimum is another n operations.
So adding a new guest = n^2+n.

For j total guests per party this comes out to j * (n^2+n)

And for k total parties this comes out to k*j*(n^2+n).

Running time is at most polynomial in n, the total number of guests. It is really less, more like nlogn and not n^2 since i grows from 1 to < n but since this is just a games forum I think we can afford to be inexact.

[jellyfish]

Oh, if you wrote this in python, sure, post it. I am writing it in c#.
Check your PM

[DeepT]

I got this mostly working, but there seems to be some undesirable statistics on how things happen to work out. Look at some sample output:

Lunch #1: 0, 1, 2, 3, 4,
Lunch #2: 5, 6, 7, 8, 9,
Lunch #3: 10, 11, 12, 13, 14,
Lunch #4: 15, 16, 17, 18, 19,
Lunch #5: 20, 21, 22, 23, 24,
Lunch #6: 25, 0, 5, 10, 15,
Lunch #7: 1, 5, 11, 16, 20,
Lunch #8: 2, 5, 12, 17, 21,
Lunch #9: 3, 5, 13, 18, 22,
Lunch #10: 4, 6, 10, 16, 21,
Lunch #11: 7, 14, 19, 23, 25,
Lunch #12: 8, 24, 0, 11, 17,

Statistics:
Guest 0 went to lunch 3 times
Guest 1 went to lunch 2 times
Guest 2 went to lunch 2 times
Guest 3 went to lunch 2 times
Guest 4 went to lunch 2 times
Guest 5 went to lunch 5 times
Guest 6 went to lunch 2 times
Guest 7 went to lunch 2 times
Guest 8 went to lunch 2 times
Guest 9 went to lunch 1 times
Guest 10 went to lunch 3 times
Guest 11 went to lunch 3 times
Guest 12 went to lunch 2 times
Guest 13 went to lunch 2 times
Guest 14 went to lunch 2 times
Guest 15 went to lunch 2 times
Guest 16 went to lunch 3 times
Guest 17 went to lunch 3 times
Guest 18 went to lunch 2 times
Guest 19 went to lunch 2 times
Guest 20 went to lunch 2 times
Guest 21 went to lunch 3 times
Guest 22 went to lunch 2 times
Guest 23 went to lunch 2 times
Guest 24 went to lunch 2 times
Guest 25 went to lunch 2 times

Guest 5 goes to lunch 5 times while guest 9 only went once. I have noticed that having more lunches or larger lunches relieves this problem. I wonder if there is some optimization that can be done to make the smaller lists more fair.

[Sidd_Budd]

I am not a programmer beyond BASIC and Pascal, but it looks like you should keep track of total number of lunches each person has attended. When selecting new lunch attendees, favor those with the least number of previous lunches.

In the example you included, after lunch #6, 4 guests (0, 5, 10, 15) have attended two lunches, the remaining guests have attended one.

When constructing lunch #7, the algorithm correctly picks guest 1, but then should skip guest 5 as a potential attendee, since guest 5 has already been selected twice. So lunch #7 should complete as 1, 6, 11, 16, 20.

[DeepT]

I do favor those with the least lunches total, however I also check for the total number lunches that a person has had with the current group.

For example guest 5 might have had 4 lunches so far, but in the current group of people going to lunch, guest 5 might not have met 3 of the people at all and 1 person once. Guest 17 who had only been to lunch 2 times, just so happens to have met everyone in that group at least once so their total lunches with the group happens to exceed guest 5's total lunches with that group even though they have been to lunch in general 2 times less than guest 5.

Still though something has to be off, when guest 9 has only been to lunch 1 time and guest 5 keeps beating it out. However this statistical problem clears itself up as you add more lunches. Go to 24 lunches and suddenly guest 9 has as many lunches as guest 5 and everyone in the list is having about the same number of lunches.

Now my algorithm picks the first best fit in a given scenario. That mean if guest 5 and guest 9 qualify equally, guest 5 wins out. I have tried choosing the last best fit and all that does is move who is screwed on lunches around, but doesn't eliminate the problem.

My first selection on picking a guest is Pick the guy who has had the least number of lunches with the people in a given group.

The next criteria is if I find that Guest 12 and Guest 14 both have the same lowest heuristic, I then ask, which one of the two have been to lunch the least number of times total? The lowest numbered one is now chosen.

That gives me the results I have. Now the next question is, if the above two heuristics are even, what is yet another one I can use to deal with this lumpiness?

[jellyfish]

Yeah, Sidd is right on the mark. We optimized for minimizing mutual party going but we do not take into account also minimizing total party going. This is only a problem during tie breaking so it is easy to fix.

When checking which guest to add to an existing party, there may be multiple potential guests who satisfy the minimum 'in party total views' requirement. So also keep track of how many total parties each guest has been to and in case of a tie take the guest with the minimum of that as well.

So change

From:
If (total_views[c]<current_min)
Then current_best_guest=c; current_min=total_views[c]

To:
If (total_views[c]<current_min) or (total_views[c]==current_min and total_parties[c]<total_parties[current_best_guest])
Then current_best_guest=c; current_min=total_views[c]

All good. I tried it with the parameters DeepT used above and the results are as desired.

[jellyfish]

DeepT, you have a bug.
In lunch # 7 after you added guest 1.
0,2,3,4 have seen guest 1 one time and 5-25 have seen guest 1 zero times.
So 5-25 are all valid candidates.
But 5,10,15 have had 2 lunches already and all the rest have had only 1. So for the tie-breaker, 5 should not be chosen but 6 should. Kick 5 out of the party.

[DeepT]

Meaning you are not getting the 1 guest with 1 lunch whereas other with 5? If that is so, I have something wrong in my implementation and currently I do not see it. Grr.

Edit: I posted this without the refresh to see the post above this one. Yes, I have a bug. Looking at it now. My boss called, and has thrown a wrench in the works, but Ill save that until I find this bug.

[Jason McCullough]

Is your boss a computer science professor?

[jellyfish]

Yeah, what is this job anyway?

[DeepT]

Jellyfish, might posting some test vectors for me? I think I found the bug, I put in an extra check in one line and the abberations have gone away. My logic is kind of tangled and I do not understand why it works yet. Ill have to look at it more on Monday. People are leaving work now so I need to bug out.

Thanks for all your help.

[DeepT]

This is an out of the blue thing that has NOTHING to do with my normal work. This guy isn't my direct boss. It is my boss's boss's boss. You got a programmer with extra cycles? Yeah? Well I have this little project I need done...

That kind of thing.

[jellyfish]

Jellyfish, might posting some test vectors for me? I think I found the bug, I put in an extra check in one line and the abberations have gone away. My logic is kind of tangled and I do not understand why it works yet. Ill have to look at it more on Monday. People are leaving work now so I need to bug out.

Thanks for all your help.

Feel free to post or PM your code if you would like a code review.

Here are 26 guests, 12 parties, 5 per party (same as your run above).

[[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14], [15, 16, 17, 18, 19], [20, 21, 22, 23, 24], [25, 0, 5, 10, 15], [1, 6, 11, 16, 20], [2, 7, 12, 17, 21], [3, 8, 13, 18, 22], [4, 9, 14, 19, 23], [24, 25, 1, 7, 13], [0, 6, 12, 18, 23]]

[DeepT]

Using your logic like:
If (total_views[c]<current_min) or (total_views[c]==current_min and total_parties[c]<total_parties[current_best_guest])
Then current_best_guest=c; current_min=total_views[c]

Didn't work for me. On the "(total_views[c]<current_min)" logic branch, I had to put the
additional logic check of "if ( LowestTotalParties >= GuestGrid[ J ][ J ] )" which is equivalent to your "total_parties[c]<total_parties[current_best_guest]". GuestGrid[ J ][ J ] contains the total parties for any given guest.

Using that, my test vectors for 26 guests at 12 parties of 5 matched your results exactly. However there is another problem and it again might be my implementation or maybe the algorithm in general. Here is the core of that part of my code:


private void AddToParty()
{
int J;
bool First = true;
int LowestSeenCount = 0;
int LowestID = 0;
int LowestTotalParties = 0;

for ( J = 0; J < GuestCount; J++ )
{
if ( Party.Contains( J ) )
{
continue;
}

int PSCount = PartySeenCount( J );

// On the first non party one, just assign our values as our baseline
if ( true == First )
{
First = false;
LowestSeenCount = PSCount;
LowestID = J;

// This will have the total parties this person has been to
LowestTotalParties = GuestGrid[ J ][ J ];
}
else
{
if ( PSCount < LowestSeenCount )
{
// The new count is actually less
if ( LowestTotalParties >= GuestGrid[ J ][ J ] )
{
LowestSeenCount = PSCount;
LowestTotalParties = GuestGrid[ J ][ J ];
LowestID = J;
}
}
else
{
// If they are equal, chose the one that has the LowestTotalCount
if ( PSCount == LowestSeenCount )
{
if ( LowestTotalParties > GuestGrid[ J ][ J ] )
{
LowestTotalParties = GuestGrid[ J ][ J ];
LowestID = J;
}
}
}
}
}

Party.Add( LowestID );
}

Remember the monkey wrench I mentioned? Well this guy (the boss's boss's boss) calls me and tells me that each guest can only go to a party (Meeting) once per month and they way it is now supposed to be run, is that you have your pool of guests, who will all be involved in one meeting per month over several months with a suggested party size of 5 or 4. So for example with 26 guests on month 1 Ill have these parties 5, 5, 4, 4, 4, 4.

I run this for the first month and everyone goes to 1 party. Seems perfect. Then I run it for 3 months in that same pattern. Suddenly I now have guests going to 4 parties and others to just 2 parties. Using the 5, 5, 4, 4, 4, 4 pattern for 3 months I get:

Lunch #1: 0, 1, 2, 3, 4,
Lunch #2: 5, 6, 7, 8, 9,
Lunch #3: 10, 11, 12, 13,
Lunch #4: 14, 15, 16, 17,
Lunch #5: 18, 19, 20, 21,
Lunch #6: 22, 23, 24, 25,
Lunch #7: 0, 5, 10, 14, 18,
Lunch #8: 1, 6, 11, 15, 19,
Lunch #9: 2, 7, 12, 16,
Lunch #10: 3, 8, 13, 17,
Lunch #11: 4, 9, 20, 22,
Lunch #12: 21, 23, 0, 6,
Lunch #13: 24, 1, 5, 12, 17,
Lunch #14: 25, 2, 8, 10, 15,
Lunch #15: 3, 7, 11, 14,
Lunch #16: 4, 13, 16, 18,
Lunch #17: 9, 19, 23, 2,
Lunch #18: 20, 24, 0, 7,

Statistics:
0 went to lunch 4 times
1 went to lunch 3 times
2 went to lunch 4 times
3 went to lunch 3 times
4 went to lunch 3 times
5 went to lunch 3 times
6 went to lunch 3 times
7 went to lunch 4 times
8 went to lunch 3 times
9 went to lunch 3 times
10 went to lunch 3 times
11 went to lunch 3 times
12 went to lunch 3 times
13 went to lunch 3 times
14 went to lunch 3 times
15 went to lunch 3 times
16 went to lunch 3 times
17 went to lunch 3 times
18 went to lunch 3 times
19 went to lunch 3 times
20 went to lunch 3 times
21 went to lunch 2 times
22 went to lunch 2 times
23 went to lunch 3 times
24 went to lunch 3 times
25 went to lunch 2 times

I really do appreciate all your help on this. I used to be into this kind of thing in college, but that is like 15 years ago and I haven't needed it since.

[DeepT]

I think I got it now. I changed the priority of least amount of parties as the most important factor with secondary consideration to who has seen the others in the group the least amount of times. The new and final AddToParty function:

private void AddToParty()
{
int J;
int LowestSeenCount = 99;
int LowestID = 99;
int LowestTotalParties = 99;

// Find the guy with the lowest total parties for our inital set
for ( J = 0; J < GuestCount; J++ )
{
if ( LowestTotalParties > GuestGrid[ J ][ J ] )
{
if ( Party.Contains( J ) )
{
continue;
}

LowestTotalParties = GuestGrid[ J ][ J ];
LowestID = J;
LowestSeenCount = PartySeenCount( J );
}
}

for ( J = 0; J < GuestCount; J++ )
{
if ( Party.Contains( J ) )
{
continue;
}

int PSCount = PartySeenCount( J );

if ( LowestTotalParties > GuestGrid[ J ][ J ] )
{
LowestTotalParties = GuestGrid[ J ][ J ];
LowestID = J;

if ( PSCount < LowestSeenCount )
{
LowestSeenCount = PSCount;
}
}
else
{
if ( LowestTotalParties == GuestGrid[ J ][ J ] )
{
if ( PSCount < LowestSeenCount )
{
LowestSeenCount = PSCount;
LowestID = J;
}
}
}

}

Party.Add( LowestID );
}

[jellyfish]

Well done DeepT.

You may have noticed by now that there are configurations where it is impossible to keep the number of guests who have seen others even.

Take for example 5 guests and 2 parties of size 2 and 3.

1st week without loss of generality:
[1,2] and [3,4,5]

2nd week without loss of generality:
[1,3] and [2,4,5]
or
[3,4] and [1,2,5]

No matter how you arrange the parties, someone saw someone else too many times.

This can be avoided if the number of parties divides evenly the number of guests. But of course this is not always possible such as when the number of guests is a prime number.

So you are left with a goal that can not always be satisfied, i.e. that all guests always see each other the same number of times. The other goal is to maintain the same number of invitations per guest. Interestingly, these goals are somewhat in competition with each other. If you put the views per guest goal first, you will end up with an imbalanced number of invitations but you will maintain the optimum, although not necessarily even, number of views per guest. If you put the balanced invitations goal first, well, this is a goal that can always be trivially satisfied, but then you end up with a sub optimal balance of views per guest.

As a final example of this point, let us replay the 5 guest example above to insure each guest sees each other guest only once per week.

1st week:
[1,2] and [1,4,5]

2nd week:
[1,3] and [1,2,4]

Each guest has seen each other guest only once per week, but some guests got invited to more parties than others.

Obviously the number of invitations per week is more of a hard limit than guests seeing each other too many times. So rightfully the order of precedence for the goals is dictated for you. You discovered this on your own.

A small consolation is that if you have hundreds of parties, the numbers will always be relatively close together. I hope you will be invited to hundreds of parties after you get a huge raise and promotion from your bosses bosses boss.

[DeepT]

I doubt Ill be getting anything more than a "Thank you" and maybe consideration for more of his pet projects. I think these parties are power lunches for groups of local business men.

It just has been so long since I have done this stuff. You get into one mode as a "Programmer" for so many years, it takes a while to wake up the "Computer Scientist" after having been asleep for so long.

Again thanks for your help.

[Zylon]

It just has been so long since I have done this stuff. You get into one mode as a "Programmer" for so many years, it takes a while to wake up the "Computer Scientist" after having been asleep for so long.
PoTAYto, poTAHto. Any but the most absolutely brain-dead monkey programming will always include an element of problem-solving.

[DeepT]

JellyFish, the boss got back to me on this one. If you still have your implementation try this:

10 guests, Party size 2.

What I have happen is that guests 9 and 10 end up having lunch together 6 times.

I know what is happening, but I am not sure what to do about it. The algorithm first picks the guys with the least amount of lunches. Then it picks the guys with the least amount of Has seen the other guests.

What happens is that it picks a very good match until it gets to the last two guys, 9 and 10. Everyone else has MORE lunches at this point so the only pairing left is last two guys who keep getting stuck together. It is kind of painting itself into a corner where 9 and 10 are the only two choices left.

I am not sure what to do about this. Any ideas?

[jellyfish]

That didn't happen to me.
Here is what I got for 20 parties...

[[0, 1], [2, 3], [4, 5], [6, 7], [8, 9], [0, 2], [1, 3], [4, 6], [5, 7], [8, 0], [9, 1], [2, 4], [3, 5], [6, 8], [7, 9], [0, 3], [1, 2], [4, 7], [5, 6], [8, 1]]
I didn't put the total number of parties as the first criterion. It is still second. I only use it as a tie-breaker. Maybe that is the difference?

[DeepT]

Maybe. Ill have to do that although I have done a lot of modifications I might have to undo. The other way I thought I would end up with people going to more parties per month then others.

Yeah, reversing the logic leaves me with some people going to more parties per month than others.

[jellyfish]

Yeah, reversing the logic leaves me with some people going to more parties per month than others.
This is inevitable. Please see my long post above. You can not optimize two competing functions simultaneously. One of them will have to take precedence at the expense of the other.

But there is still at least one more thing you can try. At each point when you are adding a guest to a party, do not add the first guest that satisfies the entry rules. Rather, generate the set of all eligible guests (i.e. attended the least parties and saw the existing guests the least total amount of times), and then if there is more than one potential guest that satisfies all of these conditions, randomly choose one of them to insert into the party. Maybe this will help.

[DeepT]

Oh, sorry there has been a change that came up that might explain this not happening with your code.

Now all these parties happen in a one month period and then it is run for N months.

So I run 10 guests for 5 parties for 12 months. Month 1 is fine, but on month 2, two guests who have met already meet again.

I think the problem is that there needs to be some kind of look-ahead. You get to some point where there are like 4 parties to make and for party 1 guests 5-10 are all equally valid. So you use guest 5. Next party set 6-10 are equally valid so you take guest 6. Eventually you are on guest 9 and the ONLY paring left is guest 10. This is a poor choice, but the only choice.

Now if we had put guest 9 in place of guest 5 we would not be in this predicament. It is just at the time of choosing guest 5 we didn't know that we were painting ourselves into a corner for some future selection we were not yet considering.

At some iteration, when I am choosing partners for guest 5, I could find the pool of all good choices, but then Id need some kind of heuristic that would figure out that guest 5 should be partnered with guest 9 (or 10 for that matter) because later on that would be beneficial.

Even looking at that I am not sure how to construct such a heuristic.

[jellyfish]

Hi. Well I seem to have overcome this latest hurdle by adding an additional heuristic.

The tie breaker for when two candidate guests both satisfy the minimum condition for inclusion into a party is as follows;

the total of the number of times this guest has seen each other guest times the number of times each other guest has been in a party.
I.e. tiebreaker(a) = sum(gi*ci) over all i.
where gi is is the number of times guest a has seen guest i and ci is the number of parties guest i has been invited to.

I guess the intuition is that this sort of avoids the overly greedy choices that can lead to problems later by preferring guests that have seen other guests few times but also taking into account the number of parties those other guests have been to.

Anyway, here is my selection for 10 guests, 2 per party, 10 parties
[0, 1], [2, 3], [4, 5], [6, 7], [8, 9], [0, 2], [4, 6], [8, 1], [3, 5], [7, 9]

Before the change this is what I had.
[0, 1], [2, 3], [4, 5], [6, 7], [8, 9], [0, 2], [1, 3], [4, 6], [5, 7], [8, 9]

Notice that previously party 7 started with guest 1.
This seemed like a good choice at the time since he is the first guest that has been to a party less than twice. But he has seen guest 0 and guest 0 has been to more parties than anyone else. In the corrected version we add guest 4 instead, and it works out.

However, my above comments in the previous post still apply. If you insist on having only one invite per month for each guest, then there are certain configurations where you can not avoid having a skewed distribution of guests that have seen each other.

[RepoMan]

This boss is obviously playing some kind of fucking Ender's Game here, where the party-goers are actually inductees into some kind of pyramid scheme, and they have to not be exposed to too many of the MLM cultists too often or they'll figure it out. Or something. No sane person would go to all this trouble unless there were serious money at stake.

[DeepT]

I did some kind of heuristic based upon the list of guests that were all equally acceptable. Out of that pool of guests, I tried to find the worst matching pair with each other, and then picked that one as the one to go to the party.

It improved it a lot. I have told this guy it is not perfect and it is as good as it is going to get and that I am DONE with this program. Hopefully I can close the book on this one.