Associated Topics || Dr. Math Home || Search Dr. Math

### 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?

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

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.

((()
(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.

more, or if you have any other questions.

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search