How to Mix People for Maximum Exposure to Each Other 1

[bsquared18]

I was asked to find an answer to the follow problem, for use in scheduling meetings of a gourmet dining club:

Suppose you have a population of individuals that may number 16, 20, or 24. These indivduals are to meet five times in different groups of four. Your goal is to sequence these four-person meetings so that over the five meetings you will maximize the exposure each individual has to the other individuals in the population. (In other words, so that each individual meets with as many of the other individuals as possible by the end of the five meetings.)

Are there any freeware or shareware programs to help with this? Or what mathematical protocol would one use?

Thanks for your help!

 

[strongm]

Ah yes, I've been to a dinner arranged like this! Never occurred to me to write a program for it though...

 

[SmokingCrater]

bsquared18,

Interesting problem...

Try this.

Assign them numbers. Person #1 - Person #20. Then, I'll explain by grid.

1 - 2 - 3 - 4
5 - 6 - 7 - 8
9 - 10- 11- 12
13- 14- 15- 16

First time, group horizontally. Group 1 composed of person 1, 2, 3 and 4. Group 2, person 5, 6, 7, and 8. Likewise.

Second time, group vertically. Group 1 composed of person 1, 5, 9, 13. Group 2, person 2, 6, 10, 14. etc.

Third, group diagonally. Group 1, persons 1, 6, 11, 16. Group 2, persons 2, 7, 12, 13. Group 3, persons 3, 8, 9, 14. etc.

Fourth, diagonally the other way. Group 1: 1, 8, 11, 14. Group 2: 2, 5, 12, 15. etc.

Fifth, group remainder. Group 1: 1, 7, 10, 15. Group 2: 2, 8, 11, 16. etc.

That should give everyone a chance to work with everone else. By my calculation it does anyway. To make 20, just add the last row in the appropriate place.

e.g. for horizontal grouping:

1 - 2 - 3 - 4
5 - 6 - 7 - 8
9 - 10- 11- 12
13- 14- 15- 16
17- 18- 19- 20

etc.

I don't know that there is an easy algorithm but that would be a solution anyway.

Othwerise, just try random!

Seriously tho, if you keep track of who has worked with who else, you could do some groupings to take advantage of who has not worked with each person. (i.e. each object keeps track of who they have worked with in the past and does not work with that person again until all have been worked with)

Hope that helps a bit. Or at least gets you thinking!

-crater

 

[kevinclark]

Sounds like a Computer Science Assignment dealing with colouring graph theorems.

The following site has a practical algorithm for scheduling Baseball tournaments, very similar to your dining problem. I have not tried the code but it may be worth your looking at the logic.

http://www.delphi3000.com/articles/article_1790.asp

 

[bsquared18]

To: "Smoking Crater"

Thanks! I filled out the 4x4 matrix, and it worked perfectly! But I'm having a problem with the 4 groups x 5 meetings (20 people) matrix. Group 5 stayed the same in 3 out of the first 4 iterations. Please check my numbers and see if I'm doing it right.

Meeting 1:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

Meeting 2:
1 5 9 13
17 2 6 10
14 18 3 7
11 15 19 4
8 12 16 20

Meeting 3:
1 6 11 16
2 7 12 13
3 8 9 14
4 5 10 15
17 18 19 20

Meeting 4:
1 8 11 14
2 5 12 15
3 6 9 16
4 7 10 13
17 18 19 20

Am I doing it wrong, or will the method work perfectly only when the number of groups and meetings are equal?

Thanks!

Bill