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.

About these ads

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, [...]

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

    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

    A Haskell solution using recursion.

    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

    @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

  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. javabloggi said

    My java solution here.

  20. 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
    
  21. jaysonsoi said

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

  22. Alcriss said

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

  23. 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]);
    }
    }

    }

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 575 other followers

%d bloggers like this: