Random Pairings that don't Repeat

Question

This little project / problem came out of left field for me. Hoping someone can help me here. I have some rough ideas but I am sure (or at least I hope) a simple, fairly efficient solution exists.

Thanks in advance.... pseudo code is fine. I generally work in .NET / C# if that sheds any light on your solution.

Given:

A pool of n individuals that will be meeting on a regular basis. I need to form pairs that have not previously meet. The pool of individuals will slowly change over time. For the purposes of pairing, (A & B) and (B & A) constitute the same pair. The history of previous pairings is maintained. For the purpose of the problem, assume an even number of individuals. For each meeting (collection of pairs) and individual will only pair up once.

Is there an algorithm that will allow us to form these pairs? Ideally something better than just ordering the pairs in a random order, generating pairings and then checking against the history of previous pairings. In general, randomness within the pairing is ok.

A bit more:

I can figure a number of ways to create a randomized pool from which to pull pairs of individuals. Check those against the history and either throw them back in the pool or remove them and add them to the list of paired individuals. What I can't get my head around is that at some point I will be left with a list of individuals that cannot be paired up. But... some of those individuals could possibly be paired with members that are in the paired list. I could throw one of those partners back in the pool of unpaired members but this seems to lead to a loop that would be difficult to test and that could run on forever.

Answer 1

at startup, build a list of all possible pairings.

add all possible new pairings to this list as individuals are added, and remove any expired pairings as individuals are removed from the pool.

select new pairings randomly from this list, and remove them from the list when the pairing is selected.

Answer 2

Your best bet is probably:

1. Load the history in a structure with fast access e.g. a HashSet of (A,B) pairs.
2. Create a completely random set of pairings (e.g. by randomly shuffling the list of individuals and partitioning into adjacent pairs)
3. Check if each pairing is in the history (both (A,B) and (B,A) should be checked)
4. If none of the pairings are found, you have a completely new pairing set as required, else goto 2

Note that step 1 can be done once and simply updated when new pairings are created if you need to efficiently create large numbers of new unique pairings.

Also note that you will need to take some extra precautions if there is a chance that all possible pairings will be exhausted (in which case you need to bail out of the loop!)

Answer 3

How about:

• create a set CI of all current individuals

then:

• randomly select one individual A and remove from CI
• create a new set of possible partners PP by copying CI and removing all previous partners of A
• if PP is empty scan the list of pairs found and swap A for an individual C who is paired with someone not in A's history and who still has possible partners in CI. Recalculate PP for A = C.
• if PP is not empty select one individual B from PP to be paired with A
• remove B from CI
• repeat until no new pair can be found

Answer 4

Interesting idea for converting a standard search into a probability selection:

• Load the history in a structure with O(1) "contains" tests e.g. a HashSet of (A,B) pairs.
• Loop through each of 0.5*n*(n-1) possible pairings
  • check if this pairing is in history
  • if not then continue to the next iteration of loop
  • increase "number found" counter
  • save pairing as "result" with probability 1/"number found" (i.e. always for the first unused pairing found)
• Finally if "result" has an answer then use it, else all possibilities are exhausted

This will run in O(n^2) + O(size of history), and nicely detects the case when all probabilities are exhausted.

Answer 5

Form an upper diagonal matrix with your elements

  Individual   A   B  C  D
           A   * 
           B   *   *
           C   *   *  *
           D   *   *  *  *

Each blank element will contain True if the pair have been formed and False if not.

Each pairing session consist of looping through columns for each row until a False is found, form the pair and set the matrix element to true.

When deleting an individual, delete row and column.

If performance is an issue, you can keep the last pair formed for a row in a counter, updating it carefully when deleting

When adding an individual, add a last row & col.

Answer 6

Based on your requirements, I think what you really need is quasi-random numbers that ultimately result in uniform coverage of your data (i.e., everyone pairs up with everyone else one time). Quasi-random pairings give you a much less "clumped" result than simple random pairings, with the added benefit that you have a much much greater control of the resulting data, hence you can control the unique pairings rule without having to detect whether the newly randomized pairings duplicate the historically randomized pairings.

Check this wikipedia entry:

http://en.wikipedia.org/wiki/Low-discrepancy_sequence

More good reading:

http://www.google.com/url?sa=t&source=web&cd=10&ved=0CEQQFjAJ&url=http%3A%2F%2Fwww.johndcook.com%2Fblog%2F2009%2F03%2F16%2Fquasi-random-sequences-in-art-and-integration%2F&ei=6KQXTMSuDoG0lQfVwPmbCw&usg=AFQjCNGQga_MKXJgfEQnQXy1qrHcwfOr4Q&sig2=ox7FB0mnToQbrOCYm9-OpA

I tried to find a C# library that would help you generate the sort of quasi-random spreads you're looking for, but the only libs I could find were in c/c++. But I still recommend downloading the source since the full logic of the quasi-random algorithms (look for quasi-Monte Carlo) is there:

http://www.gnu.org/software/gsl/

Answer 7

I see that as a graph problem where individuals are Nodes and vertex join individuals not yet related. With this reformulation create new pairs is simply to find a set of independant vertexes (without any common node).

That is not yet an answer but there is chances that this is a common graph problem with well known solutions.

One thing we can say at that point is that in some cases there may be no solution (you would have to redo some previous pairs).

It may also be simpler to consider dual graph (exchanging role of vertexes and nodes: nodes would be pairs and common individual between pairs vertexes).

Answer 8

Is there any way of ordering two elements? If so, you can save one (possibly only half) a hash probe per iteration by always ordering a pair the same way. So, if you have A, B, C and D, the generated possible pairs would be [AB, CD] [AC, BD] or [AD, BC].

What I'd do then is something like:

pair_everyone (pool, pairs, history):
  if pool is empty:
    all done, update global history, return pairs

  repeat for pool_size/2:
    pick element1 (randomly from pool)
    pick element2 (randomly from pool)
    set pair=pair(e1, e2)
    until pair not in history or all possible pairs tried:
      pick element1 (randomly from pool)
      pick element2 (randomly from pool)
      set pair=pair(e1, e2)

    if pair is not in history:
      result=pair_everyone(pool-e1-e2, pairs+pair, history+pair)
      if result != failure:
        return result
    else:
      return failure

Answer 9

Moron posted an extremely clever method a few days ago which solves this very problem, and generalizes to any size subsets - check it out.