Efficiently partition a set into all possible unique pair combinations

Question

Apologies in advance as I'm a programmer, not a mathematician. I am working on organizing pair programming in teams. So I have a set of individuals, and I want to work out all the possible unique pairing combinations so that we can have a set of pairs each day that ensures that no one re-pairs with the same person for the longest possible time.

For example, given 8 programmers:

• ["Pablo", "Dan", "Andrew", "Tom", "Rob", "Jay", "Norm", "Yev"]

I would like to be able to quickly work out a set of 7 unique possible combinations of pairs that will allow everyone to pair with someone different every day for 7 days in a row:

• [["Pablo", "Dan"], ["Andrew", "Tom"], ["Rob", "Jay"], ["Norm", "Yev"]]
• [["Pablo", "Andrew"], ["Dan", "Tom"], ["Rob", "Norm"], ["Jay", "Yev"]]
• [["Pablo", "Tom"], ["Dan", "Andrew"], ["Rob", "Yev"], ["Jay", "Norm"]]
• [["Pablo", "Rob"], ["Dan", "Jay"], ["Andrew", "Norm"], ["Tom", "Yev"]]
• [["Pablo", "Jay"], ["Dan", "Rob"], ["Andrew", "Yev"], ["Tom", "Norm"]]
• [["Pablo", "Norm"], ["Dan", "Yev"], ["Andrew", "Rob"], ["Tom", "Jay"]]
• [["Pablo", "Yev"], ["Dan", "Norm"], ["Andrew", "Jay"], ["Tom", "Rob"]]

I've written some ruby code that does this for me:

https://github.com/tansaku/pair_organiser/tree/86a1ebc1dc41b0d89cdf2116cda1f2913a28c6de

However it uses some randomization to search the space of possible pairings and it sometimes gets stuck. I've managed to get it to work for a group of up to 34 individuals, but it gets stuck like 5 or 6 times, with me needing to kill the process each time, before I eventually get a run that generates the necessary solution.

Now that's fine for the time-being, as once we've generated the correct solution for a team we can just use that solution, but it would be great to know if there is a simpler approach that would guarantee a solution. I've been searching around on the web and found a few related posts:

• https://stackoverflow.com/questions/10568081/partitioning-a-sequence-into-sets-of-unique-pairs
• Double Factorial: Number of possibilities to partition a set of $2n$ items into $n$ pairs

but I don't think that anything else I've found is addressing quite the same problem ... although I might well be wrong. Any advice or ideas very much appreciated

Answer 1

Seems like we might have the solution from Wikipedia:

One method for constructing a 1-factorization of a complete graph involves placing all but one of the vertices on a circle, forming a regular polygon, with the remaining vertex at the center of the circle. With this arrangement of vertices, one way of constructing a 1-factor of the graph is to choose an edge e from the center to a single polygon vertex together with all possible edges that lie on lines perpendicular to e. The 1-factors that can be constructed in this way form a 1-factorization of the graph.

I've adjusted my code based on that, and seems to run almost instantly for up to 34 individuals:

https://github.com/tansaku/pair_organiser

The Ruby code looks approximately like this

def factor(list) number_pairs = list.length/2 set = [] first, *rest = *list rest.each_with_index do |person, index| pairs = [] pairs << [first, person] (1..number_pairs-1).each do |offset| pairs << [rest[(index-offset)%rest.length], rest[(index+offset)%rest.length]] end set << pairs end set end

Need to run some more detailed tests for correctness. Will try to do that tomorrow.

Particular thanks to Stephen Joseph for insights into this problem

Answer 2

I programmed a dept first search (https://github.com/C9905557/pair_organiser/blob/8804ba66dee77ef29bbf7908f7f6a08b12c07ff1/lib/pairerjp.rb).

As predictable, it doesn't scale well. I got these times (in seconds) on Cloud9, for your search and mine:

# of names / your search time / my search time
8  / 0.001644534 / 0.003131525
12 / 0.029256178 / 0.010559834
16 / 0.037070159 / 0.014741157
20 / 0.289132502 / 0.622407341
24 / 0.443273171 / 24.290978803
(26 cancelled after half an hour)

One thing you can do is to precompute the results. In my search, I used only the indexes of the names, that I mapped back to the names at the end. For instance, with 8 names I got:

[[[0, 1], [2, 3], [4, 5], [6, 7]],
 [[0, 2], [1, 3], [4, 6], [5, 7]],
 [[0, 3], [1, 2], [4, 7], [5, 6]],
 [[0, 4], [1, 5], [2, 6], [3, 7]],
 [[0, 5], [1, 4], [2, 7], [3, 6]],
 [[0, 6], [1, 7], [2, 4], [3, 5]],
 [[0, 7], [1, 6], [2, 5], [3, 4]]]

that I mapped to the names with a single ruby statement:

set.map { |a1| a1.map { |a2| a2.map {|i| list[i]} } }

If you compute an integer array once for every pair integer in a range and store them, just fetch the proper one at run time and fill it with the names. I guess the the storage problem is easier to solve that the computationnal one.