Combinatorial scheduling problem

Question

In optimising a parallel computer program, I need to solve what looks like a simple combinatorial problem, but it's driving me nuts.

There are N*(N-1)/2 (i,j) tuples of all combinations of integer 0..(N-1) pairs where j > i.

For example, for N = 6, there are 15 such tuples:

(0,1) (0,2) (0,3) (0,4) (0,5) (1,2) (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5)

The problem is to rearrange those tuples into the minimum number of rows such that the same integer never occurs more than once in each row. For example, a solution for N = 6 would be:

(0,1) (2,3) (4,5)
(0,2) (1,4) (3,5)
(0,3) (1,5) (2,4)
(0,4) (1,3) (2,5)
(0,5) (1,2) (3,4)

I solved this by hand for several values of N including N = 16, and I believe a trial-and-error backtracking algorithm exists for general N, though that looks to be NP-hard.

Unfortunately, I don't see an obvious pattern in the solutions I found.

Is there a simple pattern or a simple algorithm to solve this for general N, please?

Thanks and kind regards, Peter McGavin.

Answer 1

It turns out it's the same as the "Round-robin tournament" scheduling problem.

Solutions include the "Circle method", "Berger tables" and Richard Shurig's "pairing tables".

https://en.wikipedia.org/wiki/Round-robin_tournament

Answer 2

Here is how you succeed when $n$ is odd.

The $i^\text{th}$ row will pair up all numbers besides $i$, for each $i$ ranging from $0$ to $n-1$. Specifically, $\{x,y\}$ is a pair exactly when $$ (x+y-2i)\;\%\;n =0 $$ The percent sign is the modulo operation.