generating all pairs

Question

suppose I have 6$\{0,1,2,3,4,5\}$ numbers.I should generate following 4 pairings of numbers where there will be 3 pairs in each pairing s.t

• each number should be in one pair and also every number should be paired

• a pair(like 0-1) should be present in only one of the pairing. and also every possible pair should be present somewhere

i) 0-1 , 2-3 ,4-5

ii) 0-4 , 1-2 ,3-5

iii) 0-3 , 1-4 ,2-5

iv) 0-2 , 1-5 ,3-4

v) 0-5 , 1-3 ,2-4

similarly if I have N numbers. I need $(N-1)$ pairing of numbers s.t in each pairing there are $N/2$ pairs.

essentially this is grouping $\binom{n}{2}$ combinations into $n-1$ groups s.t each number is present exactly once in each group

Answer 1

As pointed out by @Pseudonym, this problem is identical to finding a round robin tournament schedule. A straightforward implementation would be the following:

def get_sets(a: list):
    # Simple implementation of
    # https://nrich.maths.org/1443
    center, *rest = a
    for _ in range(len(rest)):
        rest = rest[1:] + rest[:1] # put 1st element to back of list
        solution = [[center, rest[len(rest) // 2]]] # combine middle element with center
        for i in range(len(rest) // 2):
            solution.append([rest[i], rest[~i]]) # combine i-th element from front with i-th from back
        yield solution

for s in get_sets(list(range(50))):
    print(s)

Note that this implementation creates a new list for each "set" in the output. This is not strictly necessary, as the same result could be achieved by using only the initial list (actually array) and use smart indexing.

Answer 2

Your problem is related to the balanced tournament design problem.

Suppose that you have $2n$ tennis players, there are $n$ tennis courts, and you need to play a round robin tournament in $2n-1$ rounds. The courts aren't the same, to to balance the effect of the different courts, you want to ensure that no player competes more than twice on any one court. The problem is to design the rounds.

Formally, a BTD of order $n$ is an arrangement of all of the distinct (unordered) pairs of a set $V$ (where $|V| = 2n$) into a $n$ by $2n-1$ array such that:

• Every element of $V$ appears precisely once in each column.
• Every element of $V$ appears at most twice in each row.

While your problem isn't exactly the same as the BTD problem, any solution to the BTD problem is a solution to your problem. So a solution to the BTD problem solves your problem if $N$ is even. (I don't know what you want to do if $N$ is odd.)

The BTD problem has a very simple solution. See, for example, this blog post by Rachel Silverman.