How can one assign n people pairwise to n-1 tables, in a speed-date fashion, such that no two persons meet twice and each person is at each table exactly once? Does this problem have a name?

The problem in full

Given n people (n is even), assign them in pairs in n-1 rounds. Each round represent a list of n/2 pairs, each pair being two individuals that have not met earlier.

For each round, find a match between the n/2 pairs and n-1 tables, so that every pair are assigned a table. The tables are unique. Through all n-1 rounds, an individual should meet each other individual exactly once, and be at each table exactly once.

What have I tried?

Here is the naive bipartite matching algorithm I've created so far:

  1. Create rounds using the round-robin tournament scheduling.
  2. Represent each round as a bipartite graph, pairs vs tables.
  3. For each round, find a match.
    • For each player, remove table matched in this round.

In pseudo:

n = 6
tables = [1, 2, 3, 4, 5]
players = [{'i': 1, 'tables': copy(tables)}, {'i': 2, 'tables': copy(tables), ...]
rounds = roundRobin(players)
# each round has a list of pairs
# each pair is two players
# [ 
#     [[1,6], [2,5], [3,4]], 
#     [[1,2], [3,6], [4,5]], 
#     ...
# ]
matches = []
# keep matches

for round in rounds:
    match = hopcroft_karp(round, tables)
    # pair 1 to table 1, ...
    # [ [1, 1], [2, 2], [3, 3] ]

    if len(match) !== len(round):
        # TODO: backtrack
        add match to matches
        for edge in match:
            pair = round[edge[0]]
            table = edge[1]
            removeTable(pair[0], table)
            removeTable(pair[1], table)


For some n, there is no solution. For example n = 4. I'm unsure for which n the problem has solutions. Here is n = 4 as an example:

People: 1, 2, 3, 4
Tables: A, B, C

Round 1: A:1,2 - B:3,4
      In round 1, we can assign tables at random, because
      the problem is the same with renaming tables.
Round 2: C:1,3 - ?:4,2 <-- not possible
      4 has already been at table B. 
      2 has already been at table A. 
      Table C is taken by pair 1,3.
Round 3: ?:1,4 - ?:2,3 <-- same as round 2
  • $\begingroup$ Thanks for your feedback. I've edited the question, hope it's more clear now. What I want answered is in the top. Mainly, how to solve the problem. I think the main obstacle lies in the backtracking, maybe creating a data-structure that allows that. If not, my take and the pseudo code can probably be discarded. $\endgroup$ – arve0 Sep 23 '17 at 18:55
  • $\begingroup$ I have no idea what you're asking. Can you give an example of a legal schedule for various values of $n$? $\endgroup$ – Yuval Filmus Sep 24 '17 at 7:39
  • $\begingroup$ @YuvalFilmus I've added an example, which has no solution, but should shed light on what is the problem. Finding a legal schedule is the problem, so I do not have any legal schedules as of now. If anything else is unclear, please let me know. $\endgroup$ – arve0 Sep 24 '17 at 9:28

Your problem seems to be the same as that of constructing a Room square. Let me quote from The existence of Room squares by Mullin and Wallis:

A Room square of side $2n+1$ is a $2n+1$ by $2n+1$ array of cells and a set $S$ of $2n+2$ objects called symbols which satisfy the following conditions:

(i) Every cell of the array is either empty or contains an unordered pair of distinct symbols from $S$.

(ii) Each symbol occurs in every row and column of the array.

(iii) Every unordered pair of symbols occurs precisely once in the array.

Mullin and Wallis state that a Room square of size $v$ exists for all odd positive $v$ except for $v=3,5$. This explains why your construction for $n=4$ (which corresponds to $v=3$) wasn't successful.

To construct a Room square, look into the article Construction of Room Squares by Stanton and Mullin.

  • 1
    $\begingroup$ I've not yet been able to generate a patterned starter, as I haven't grokked the paper. But I've created a package which generates Room Squares from k=7 to k=47 by using the starters found in the paper. npmjs.com/package/room-squares $\endgroup$ – arve0 Sep 26 '17 at 17:44

Your Answer

