Lab Partner PairingsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/