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

[…] 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):

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

part [x] = []

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

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

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:

Example run:

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:

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:

A 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