2
$\begingroup$

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
    else:
        add match to matches
        for edge in match:
            pair = round[edge[0]]
            table = edge[1]
            removeTable(pair[0], table)
            removeTable(pair[1], table)

Example

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
$\endgroup$
  • $\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
2
$\begingroup$

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.

$\endgroup$
  • 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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.