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

Pages: 1 2

### 25 Responses to “Pairing Students”

1. […] today’s Programming Praxis exercise, our goal is to produce all combinations of two elements of a list, […]

```import Data.List

pairs :: [a] -> [(a, a)]
pairs xs = [(a,b) | (a:bs) <- tails xs, b <- bs]
```
3. Tante Hedwig said

input = ["Anna","Beth","Chaim","Dirk"]

part [x] = []
part (x:xs) = (x,xs) : part xs

teacher inp = [(hd,b) | (hd,tl) <- part inp, b <- tl]

4. Hm, looking at it some more it seems I misinterpreted the assignment. My code produces all pairings, not all sets of pairings.

5. geir said

import sys

def pair(group):
def pair_aux(first, rest):
if rest == []:
return []
return [(first, rest)] + pair_aux(first, rest[1:]) + pair_aux(rest,rest[1:])
return pair_aux(group, 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’)]

6. 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?

7. […] my initial attempt of today’s Programming Praxis exercise, I misunderstood the problem. Rather than producing all sets of pairs, […]

8. My new solution (see http://bonsaicode.wordpress.com/2013/05/03/programming-praxis-pairing-students-revisited/ for a version with comments):

```import Data.List

pairSets :: Eq a => [a] -> [[(a, a)]]
pairSets [] = [[]]
pairSets (x:xs) = concat [(map ((x,b) : ) . pairSets \$ delete b xs) | b <- xs]
```
9. Mike said
```def pairs(students):
def _pairs(xs, ps):
if len(xs) <= 2:
yield ps + [tuple(xs)]
else:
for i in range(1,len(xs)):
yield from _pairs(xs[1:i] + xs[i+1:], ps + [(xs, xs[i])])

yield from _pairs(students, [])
```
10. ben said

f [] pairings = concat pairings
f (student:students) pairings = f students \$ zip (repeat student) students : pairings

buildGroups students = f students []

11. aks said

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, pair }

exit
```

Example 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}
```
12. aks said

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}
```
13. eupraxia said
```# 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}}
```
14. eupraxia said
```# more efficient?
pairs = lambda names: [(x, y) for x in names for y in names[names.index(x)+1:]]
```
15. namako said

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.

16. ben said

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

17. namako said

@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.

18. Colin said

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”.

19. […] Question is from here: […]

20. javabloggi said

My java solution here.

21. 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
end
```
22. jaysonsoi said

A C# Solution:
int _arrSize = 0;
Console.WriteLine(“Input array size:”);
string[] _arrNames = new string[_arrSize] ;
for (int i = 0; i < _arrSize; i++)
{
Console.WriteLine("Input Name {0}: ", i + 1);
}

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] + "}") ;
}
}

23. Alcriss said

string pair = string.Empty;
int here = 0;

Console.Write(“Enter names: “);

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);
}
}

}
//METHOD

public static string Pair(string name1, string name2)
{
return "\n { " + name1 + ", " + name2 + " }";
}

24. brice said

``` #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]); } } ```

```} ```

25. hakim said

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