1

I'm speaking with reference to Scheduling algorithm for a round-robin tournament?.

I need to pair (or triple) a group of people into trios, in order for them to meet. For example, in a group of 9 people, the first meetings would be: [1, 2, 3], [4, 5, 6], [7, 8, 9]. Next meetings would be something like [1, 4, 7], [2, 5, 8], [3, 6, 9]. Things end when everyone has met everyone else, and we need to minimize the number of "rounds".

I'm at wit's end thinking of the solution to this. Many thanks to someone who can point me in the right direction :)

Community
  • 1
  • 1
Daryll Santos
  • 2,031
  • 3
  • 22
  • 40

1 Answers1

1

If "everyone has met everyone else" means that all pairs appear in the schedule, then this is a generalization of Kirkman's schoolgirl problem, solvable in the minimum number of rounds when there is an odd number of groups (existence of Kirkman triple systems, due to Ray-Chaudhuri and Wilson). The social golfer problem is a generalization to other group sizes, and I expect that the situation for even numbers of groups would be studied under that name.

In the (seemingly unlikely) event that "everyone has met everyone else" means that all possible groups have been used, then you want to use the construction in Baranyai's theorem to find hypergraph factors (see my previous answer on the topic for a Python implementation).

Community
  • 1
  • 1
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120