Pairing Students

May 3, 2013

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. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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[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')]

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[0], 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[0], pair[1] }

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