Pairing Students
May 3, 2013
There is a trick from the programming folklore that makes this problem simple; it probably originated with gym teachers who want to make randomly equal teams over the course of a semester, using an algorithm to choose sides instead of letting students form up their own sides. The idea is to line up the students in two rows, then hold the first student in place while the other students rotate. It looks like this for six students:
1 2 3 1 4 2 1 5 4 1 6 5 1 3 6 — clockwise
4 5 6 5 6 3 6 3 2 3 2 4 2 4 5
1 2 3 1 3 6 1 6 5 1 5 4 1 4 2 — counter-clockwise
4 5 6 2 4 5 3 2 4 6 3 2 5 6 3
At each step the five students 2, 3, 4, 5 and 6 rotate clockwise — we could equally choose to rotate counter-clockwise. Students in the same column are paired, so in the first set the three pairs are {1,4}, {2,5}, and {3,6}. Over the five sets of pairings student 1 is paired with 4, 5, 6, 2, and 3, in order from left to right, so there are no duplicates, and the same is true for all of the other students. Here’s the program:
(define (pairs xs)
(let loop ((n (length xs)) (xs xs) (xss (list)))
(if (= n 1) (reverse xss)
(loop (- n 1) (cons (car xs) (cdr (rotate xs)))
(cons (make-set xs) xss)))))
We separate the step of building the output from the generation of the rotations above:
(define (make-set xs)
(call-with-values
(lambda () (split (/ (length xs) 2) xs))
(lambda (front back)
(let loop ((front front) (back back) (xss (list)))
(if (null? front) (reverse xss)
(loop (cdr front) (cdr back)
(cons (sort < (list (car front) (car back))) xss)))))))
Rotating is harder than it looks. A simple cyclic rotation doesn’t work, as shown below; notice that (2 5), (3 6), (2 4), and (4 6) are repeated:
1 2 3 1 3 4 1 4 5 1 5 6 1 6 2 — cyclic — doesn’t work
4 5 6 5 6 2 6 2 3 2 3 4 3 4 5
Here is our version of rotate, which uses list-handling primitives last and but-last:
(define (last xs) (car (reverse xs)))
(define (but-last xs) (reverse (cdr (reverse xs))))
(define (rotate xs)
(call-with-values
(lambda () (split (/ (length xs) 2) xs))
(lambda (front back)
(append (list (car front)) (list (car back))
(but-last (cdr front))
(cdr back) (list (last front))))))
And here is some sample output:
> (pairs '(1 2 3 4))
(((1 3) (2 4))
((1 4) (2 3))
((1 2) (3 4)))
> (pairs '(1 2 3 4 5 6)
(((1 4) (2 5) (3 6))
((1 5) (4 6) (2 3))
((1 6) (3 5) (2 4))
((1 3) (2 6) (4 5))
((1 2) (3 4) (5 6)))
> (pairs '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16))
(((1 9) (2 10) (3 11) (4 12) (5 13) (6 14) (7 15) (8 16))
((1 10) (9 11) (2 12) (3 13) (4 14) (5 15) (6 16) (7 8))
((1 11) (10 12) (9 13) (2 14) (3 15) (4 16) (5 8) (6 7))
((1 12) (11 13) (10 14) (9 15) (2 16) (3 8) (4 7) (5 6))
((1 13) (12 14) (11 15) (10 16) (8 9) (2 7) (3 6) (4 5))
((1 14) (13 15) (12 16) (8 11) (7 10) (6 9) (2 5) (3 4))
((1 15) (14 16) (8 13) (7 12) (6 11) (5 10) (4 9) (2 3))
((1 16) (8 15) (7 14) (6 13) (5 12) (4 11) (3 10) (2 9))
((1 8) (7 16) (6 15) (5 14) (4 13) (3 12) (2 11) (9 10))
((1 7) (6 8) (5 16) (4 15) (3 14) (2 13) (9 12) (10 11))
((1 6) (5 7) (4 8) (3 16) (2 15) (9 14) (10 13) (11 12))
((1 5) (4 6) (3 7) (2 8) (9 16) (10 15) (11 14) (12 13))
((1 4) (3 5) (2 6) (7 9) (8 10) (11 16) (12 15) (13 14))
((1 3) (2 4) (5 9) (6 10) (7 11) (8 12) (13 16) (14 15))
((1 2) (3 9) (4 10) (5 11) (6 12) (7 13) (8 14) (15 16)))
We used split from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/dYKX6r0x.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to produce all combinations of two elements of a list, […]
My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/03/programming-praxis-pairing-students/ for a version with comments):
Hm, looking at it some more it seems I misinterpreted the assignment. My code produces all pairings, not all sets of pairings.
import sys
def pair(group):
def pair_aux(first, rest):
if rest == []:
return []
return [(first, rest[0])] + pair_aux(first, rest[1:]) + pair_aux(rest[0],rest[1:])
return pair_aux(group[0], group[1:])
if __name__ == ‘__main__’:
group = sys.argv[1:]
print pair(group)
~>python pairing.py anne beth chet dirk
[(‘anne’, ‘beth’), (‘anne’, ‘chet’), (‘anne’, ‘dirk’), (‘chet’, ‘dirk’), (‘beth’, ‘chet’), (‘beth’, ‘dirk’), (‘chet’, ‘dirk’)]
Hm, either I’m still not understanding the assignment correctly or the provided solution is wrong. I’ve modified my program and for the version with 6 students I get the following combinations:
[(1,2),(3,4),(5,6)]
[(1,2),(3,5),(4,6)]
[(1,2),(3,6),(4,5)]
[(1,3),(2,4),(5,6)]
[(1,3),(2,5),(4,6)]
[(1,3),(2,6),(4,5)]
[(1,4),(2,3),(5,6)]
[(1,4),(2,5),(3,6)]
[(1,4),(2,6),(3,5)]
[(1,5),(2,3),(4,6)]
[(1,5),(2,4),(3,6)]
[(1,5),(2,6),(3,4)]
[(1,6),(2,3),(4,5)]
[(1,6),(2,4),(3,5)]
[(1,6),(2,5),(3,4)]
There are a number of those that you do not produce, such as 1+2, 3+5, 4+6 and 1+2, 3+6, 4+5, which seem like valid sets to me. So which one of us is doing something wrong?
[…] my initial attempt of today’s Programming Praxis exercise, I misunderstood the problem. Rather than producing all sets of pairs, […]
My new solution (see http://bonsaicode.wordpress.com/2013/05/03/programming-praxis-pairing-students-revisited/ for a version with comments):
A Haskell solution using recursion.
f [] pairings = concat pairings
f (student:students) pairings = f students $ zip (repeat student) students : pairings
buildGroups students = f students []
Ruby solution:
#!/usr/bin/env ruby # pairs.rb [list of names] # # A teacher wants to create several sets of pairs of her students to work # together on class projects; over the several sets, each student should be # paired with each other student only once. For instance, with four students, # there are three sets of pairings: # {Anne, Beth}, {Chet, Dirk} # {Anne, Chet}, {Beth, Dirk} # {Anne, Dirk}, {Beth, Chet} # # Your task is to write a program that, given a list of students, produces a # list of all possible sets of pairings, without duplicates. Names = %w( Anne Beth Chet Dirk Alan John Mary Joey Fred ) if ARGV.size < 1 names = Names else names = ARGV end names = names.sort.uniq pairs = [] while names.size > 0 name1 = names.shift names.each {|name2| pairs += [[name1, name2]]} end pairs.each {|pair| printf "{%s, %s}\n", pair[0], pair[1] } exitExample run:
$ ./pairs.rb Anne Beth Chet Dirk {Anne, Beth} {Anne, Chet} {Anne, Dirk} {Beth, Chet} {Beth, Dirk} {Chet, Dirk} $ ./pairs.rb Anne Beth Chet Dirk Alan John {Alan, Anne} {Alan, Beth} {Alan, Chet} {Alan, Dirk} {Alan, John} {Anne, Beth} {Anne, Chet} {Anne, Dirk} {Anne, John} {Beth, Chet} {Beth, Dirk} {Beth, John} {Chet, Dirk} {Chet, John} {Dirk, John}Here is a bash version:
# Default name list (for testing)
names=( Anne Beth Chet Dirk Alan John Mary Joey Fred )
if [[ $# -ge 1 ]]; then
names=( "$@" ) # get names from command line
fi
sort_uniq() {
echo "$@" | tr ‘ ‘ ‘\12’ | sort -u | tr ‘\12’ ‘ ‘
}
# sort and uniq the names
names=($( sort_uniq "${names[@]}" ))
len=${#names[*]}
pairs=()
x1=0
while [[ $x1 -lt $len ]] ; do
name1="${names[$((x1++))]}"
x2=$x1
while [[ $x2 < $len ]] ; do
name2="${names[$((x2++))]}"
echo "{$name1, $name2}"
done
done
exit
The output:
$ ./pairs.sh Anne Beth Chet Dirk {Anne, Beth} {Anne, Chet} {Anne, Dirk} {Beth, Chet} {Beth, Dirk} {Chet, Dirk} $ ./pairs.sh Anne Beth Chet Dirk Alan John {Alan, Anne} {Alan, Beth} {Alan, Chet} {Alan, Dirk} {Alan, John} {Anne, Beth} {Anne, Chet} {Anne, Dirk} {Anne, John} {Beth, Chet} {Beth, Dirk} {Beth, John} {Chet, Dirk} {Chet, John} {Dirk, John}# set comprehensions require Python 2.7 or higher. pairs = lambda names: {tuple(sorted((x, y))) for x in names for y in set(names)-{x}}Aren’t these lists rather gigantic? A bit of legwork gives, for n distinct students,
nsets (2n) = (2n)! / (n!2^n)
nsets (2n+1) = (2n+1)(2n)! / (n!2^n) = nsets(2(n+1))
Something like O(n!2^n) sets of pairs. Seems like a pretty hellish memory requirement to me.
For example my physics class at A-level was something like 20 students, which comes to 654729075 possible sets of pairings.
@namako, you are thinking about this the wrong way.
f [] ys = concat ys
f (x:xs) ys = f xs $ zip (repeat x) xs : ys
— from the example given above we know that the outcome must be 6.
*Praxis1> length $ f [“Anne”,”Beth”,”Chet”,”Dirk”] []
6
— so everything checks out… Now if we had 20 students, represented by a list [1..20] :
*Praxis1> length $ f [1..20] []
190
@ben
Aren’t we looking for sets of pairings? Maybe I’m reading it differently, but it looks like the problem is to find all the ways to split the class into pairs, cf. “…produces a list of all possible sets of pairings, without duplicates.”, which produces the excessive number of possibilities. ‘All possible pairs’ will produce nC2 (20C2 = 190) results. Furthermore the preamble is 3 pairs of pairs.
Though going by these comments only Remco Niemeijer is reading it the same way, so maybe I’m wrong. Looking at it, the example code seems to support this reading too, as it’s printed a list of lists of pairs. It happens that both approaches produce the same number of results for six students (6C2 = 15 = nsets(6)) as well so it doesn’t really give a good test to separate these approaches.
I also find the description confusing; “Given a list of students, produc[e] a list of all possible sets of pairings, without duplicates.”
I think a “set of pairings” is clear enough from the description and example–a function mapping each student to a partner, such that the partner also maps back to the original student.
(I’ll change to using the word “round” to describe a “set of pairings”.)
“All possible” implied to me that each possible “round” should be represented.
I could not figure out what “without duplicates” meant. If it meant that each student was represented only once in each “set of pairings”, then that seemed redundant with “set of pairings” as described above.
This led me to develop a solution that corresponds to Remco’s. As namako says, the output grows very very fast with respect to n.
The given solution _one_ “tournament” for the 2n students, in the form of (2n-1) “rounds”, in which each possible pair is represented exactly once: a “round-robin” tournament.
However, for any (2n > 4), the solution is not unique, even under permutation of the “rounds”.
[…] Question is from here: […]
My java solution here.
A Ruby solution:
def pairings(students) pairs = [] students[0...-1].each_index do |i| students[(i+1)..-1].each{|bud| pairs << [students[i], bud]} end pairs endA C# Solution:
int _arrSize = 0;
Console.WriteLine(“Input array size:”);
_arrSize= Convert.ToInt32(Console.ReadLine());
string[] _arrNames = new string[_arrSize] ;
for (int i = 0; i < _arrSize; i++)
{
Console.WriteLine("Input Name {0}: ", i + 1);
_arrNames[i]=Console.ReadLine();
}
Console.WriteLine("\nProbable Pairs:\n");
for (int i = 0; i < _arrNames.Length – 1; i++)
{
for (int x = i+1; x < _arrNames.Length ; x++)
{
Console.WriteLine("{"+ _arrNames[i]+", " +_arrNames[x] + "}") ;
}
}
Console.ReadLine();
string pair = string.Empty;
int here = 0;
Console.Write(“Enter names: “);
string[] userInput = Console.ReadLine().Split(‘ ‘);
for (int i = 1; i <= userInput.Length; i++)
{
if (i == userInput.Length)
{
here += 1;
i = 0 + here;
}
else
{
pair = Pair(userInput[here], userInput[i]);
Console.Write(pair);
}
}
Console.ReadLine();
}
//METHOD
public static string Pair(string name1, string name2)
{
return "\n { " + name1 + ", " + name2 + " }";
}
#include
#include
char * students[] = {
"Anne", "Beth", "Chet", "Dirk", NULL
};
int main (int argc, char* args[]){
printf("Starting...\n");
int i,j;
for ( i = 0; students[i] != NULL; i++){
for ( j = i+1; students[j] != NULL; j++){
printf("%s %s\n", students[i], students[j]);
}
}
}
groovy solution
def result =[] as Set
def students =[‘Anne’, ‘Beth’, ‘Chet’, ‘Dirk’]
0.upto(students.size()-2){pos->
students[pos+1 .. students.size()-1].each(){it->
result << [students[pos],it]
}
}
println result