Lab Partner Pairings

Date: 01/21/2001 at 22:45:08
From: Don Maynard
Subject: Finding lab partner pairs in a class of 22

A friend who is a teacher would like to find all the possible pairings 
of his 22 students for science labs. Is there an algorithm for this? 

It's a problem that is much more complicated than it appears at first 
sight. There should be 11 pairs and no student should be paired to the 
same other student twice in the series. I wrote a program that could 
list up to 14 pairings, but that was not satisfactory because we 
wanted to find all possible lists and be assured that they were all 
there. Any ideas? 

Thanks for your consideration.

Don Maynard
American School in Japan

Date: 01/29/2001 at 11:52:31
From: Doctor Ian
Subject: Re: Finding lab partner pairs in a class of 22

Hi Don,

If I understand your question correctly, you are using the word 
'pairing' in the following way. A class of four students has the 
following pairings:

   Pairing 1:  AB CD 
   Pairing 2:  AC BD
   Pairing 3:  AD BC

If this is the correct interpretation, then you can generate all the
possible pairings in the following way.  

I'll use the following data structure to represent a single pairing.  
It's a list that contains two other lists. The first list is a list of 
student pairs. (Each pair is itself a list.) The second list is a list 
of unpaired students. 
 
  (((a b) (c d))            The pairing so far.
   (e f g h))               Students yet to be paired.


Start with list containing a single empty pairing:

  ((()
    (a b c d)))

From this, generate the set of possible first pairs, and make a new 
pairing that begins with each of those pairs:

  ((((a b))
    (c d))
   (((a c))
    (b d))
   (((a d))
    (b c))
   (((b c))
    (a d))
   (((b d))
    (a c))
   (((c d))
    (a b))

Note what we did here - we took each possible pair from the list of
unpaired students, and added that pair to the pairing. Then we removed
those students from the unpaired list. Each pair gives rise to a 
completely new pairing. 

Now do the same thing over again:

  ((((a b) (c d))
    ())
   (((a c) (b d))
    ())
   (((a d) (b c))
    ())
   (((b c) (a d))
    ())
   (((b d) (a c))
    ())
   (((c d) (a b))
    ())

Each pairing is expanded until its unpaired list is empty, at which 
point the pairing is complete. Note that in the general case (i.e., 
more than two unpaired students), each pairing will give rise to 
several new pairings each time a new pair is selected, e.g.:

  (((a f) (c e))
   (b d g h))
  =>
  (((a f) (c e) (b d))
   (g h))
  (((a f) (c e) (b g))
   (d h))
  (((a f) (c e) (b h))
   (d g))
  (((a f) (c e) (d g))
   (b h))
  (((a f) (c e) (d h))
   (b g))
  (((a f) (c e) (g h))
   (b d))
  
In fact, a pairing with N unpaired students will give rise to 
N*(N-1)/2 new pairings.  
            
Note that this algorithm will generate some duplicate pairings. But 
you can sort all the pairings, which will force duplicates to appear 
next to each other, making them easy to find and remove: 

  ((a b) (c d))
  ((a c) (b d))
  ((a d) (b c))
  ((b c) (a d))
  ((b d) (a c))
  ((c d) (a b))

  == sort ==>

  ((a b) (c d))
  ((a b) (c d))
  ((a c) (b d))
  ((a c) (b d))
  ((a d) (b c))
  ((a d) (b c))

  == remove duplicates ==>

  ((a b) (c d))
  ((a c) (b d))
  ((a d) (b c))

In fact, since the number of possible pairings for 22 students is 
going to be VERY large, you might want to so this sort-and-remove step 
after each round of selections, instead of waiting until the end.  

I've used notation from the Lisp programming language, which is 
ideally suited for this kind of thing; but you should be able to 
implement the same algorithm in just about any programming language. 

I hope this helps.  Write back if you'd like to talk about this some 
more, or if you have any other questions. 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/