Grouped Combinations Algorithm

Question

My nephew has a new business that unites business people for coffee and conversation. It's kind of like musical chairs. After a given amount of time, everyone gets up an moves to a different table. The idea is that everyone has to have the opportunity to talk to each person. He's trying to figure out how to do it with 16 people and 4 tables where everyone moves 5 times.

I wanted to figure out an algorithm to do that, but I found the problem is much more challenging than I imagined at first. To simplify it, I worked out how to do it with 6 people and 3 tables. It can be represented as follows:

Step 1: (1, 2), (3, 4), (5, 6)
Step 2: (1, 3), (2, 5), (4, 6)
Step 3: (1, 4), (2, 6), (3, 5)
Step 4: (1, 5), (2, 4), (3, 6)
Step 5: (1, 6), (2, 3), (4, 5)

One possibility, which wouldn't be very efficient, would be to generate all the possible combinations and eliminate any that are mutually exclusive. However with odd combinations, that wouldn't be possible. For example, if there were 6 people with only 2 tables, there would be two people sitting at the same table more than once. Of course, the idea of the algorithm is to have everyone meet at least once in the shortest number of steps.

Answer 1

This is called the social golfer problem. The link goes to a solution for the 16-person, 4-table case, reproduced here.

ABCD EFGH IJKL MNOP
AEIM BFJN CGKO DHLP
AFKP BELO CHIN DGJM
AGLN BHKM CEJP DFIO
AHJO BGIP CFLM DEKN

This problem is in general very hard; solutions are found either by mathematical constructions that do not work for all parameter settings or by lengthy constraint satisfaction computations.

Answer 2

Pé, I saw you are also interested in APL, so you may like an APL algorithm to do this:

http://dfns.dyalog.com/n_pmat.htm