2

I was recently asked the following seemingly simple question: What is the best way to partition a team of 12 people into groups of three, where the process is to be repeated 6 times? The solution should minimize the number of times two people are put together in the same team. The total number of combinations is given by,

nCr = 12!/(3! * (12-3)!) = 220

so finding a solution by hand is not really a practical proposition. The most practical (and simplistic) solution that I found was to shuffle the 12 names and select the groups from the 1st, 2nd, 3rd and 4th triples. Then run the process 6 times. This did solve the problem, but there were too many situations where two people were put together in the same group, after consecutive runs. A general solution (groups of r from n) would be nice.

I have also posted this on "Computational Science" but they feel it belongs elsewhere. I have looked at link1 and link2 but these solutions do not seem to solve my particular problem.

Graham G
  • 551
  • 5
  • 14
  • maybe more suited for statexchange? – chinsoon12 Jun 02 '20 at 10:05
  • To get a random result you could do `lapply(1:6, function(i) matrix(sample(1:12), 3, 4))` But probably it's better to ask this on [math.stackexchange](https://math.stackexchange.com/help/on-topic). – jay.sf Jun 02 '20 at 11:44
  • 2
    Here is a possible starting point: https://math.stackexchange.com/questions/1435341/divide-120-students-into-12-groups-for-6-workshops-without-repeating/1435777#1435777 – Dave2e Jun 02 '20 at 13:13

1 Answers1

2

This problem is a variant of the "Social Golfer Problem", which is an open problem in graph theory. Many thanks to Dave2e who provided a clue to its solution by the Link1. This link leads to two more excellent discussions of the problem at Link2 and Link3.

Graham G
  • 551
  • 5
  • 14
  • 2
    Thank goodness for that. I have tried several times to solve your problem programatically and couldn't get past four days of scheduling. I knew six was impossible but thought there was probably a way to get five days then repeat day one as the optimal solution. It seems from the links that this isn't possible, so I can stop beating myself up! – Allan Cameron Jun 04 '20 at 15:07
  • 1
    It was also a great relief to me when I found it was an open problem and I had to be satisfied with a sub-optimal solution. – Graham G Jun 05 '20 at 10:23