[Math] Efficiently partition a set into all possible unique pair combinations

algorithmscombinations

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:

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

Best Answer

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.

enter image description here

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

Related Question