Algorithm for Grouping

Question

I am trying to help someone write a program that I thought would be easy, but of course it never is :)

I am trying to take a class roster (usually between 10-20 students) and effectivly uniquely pair off each classmate to another to make unique groups. Therefore in a class of 10 people, you can have 9 groups.

It needs to be able to handle odd number of students too, adding to my confusion.

I was looking at doing this in Java, but that is flexible. Any ideas on an algorithmic way to guarantee a)not infinite looping (ending with 2 people who have already been partners) and b) I am aiming for more efficent time than space, since class size will be small!

Thanks!

Answer 1

You want to create a complete graph with each student as a node, then randomly select edges and insert them into a unique set.

On the next "pull", you want to do the same thing, except now if the edge has already been selected, discard and reselect.

Answer 2

This is an unusual answer for me - to say "download an application" - but here you go:

What you describe may be similar enough to Chess Tournament Pairing.

Check this out: http://home.swipnet.se/rullchef/chessp/

Here's an explanation of the Monrad system which may be what you're after:

Monrad System

The Monrad system is a very interesting variation of the cup system, which to my knowledge is only used on a regular basis in chess tournaments. In the first round all teams are paired randomly. The winner gets 1 point and the looser zero. In each successive round all teams with the same number of points are paired randomly (except that teams which earlier have played each other can not be paired if there are other pairing possibilities). This system has the advantage, that all teams keep playing, in contrast to the cup system, and as the season (or tournament) advances teams with equal strength will be meeting each other. There are no limitations to the number of rounds that can be played, but eventually teams have to be paired if they have similar, but not necessarily identical, number of points. The team with the largest number of points after a predefined set of rounds is the winner.

Answer 3

I'm not sure how well this will work, but here it goes:

Say there are 6 students, let's call them A-F. They sit in 2 rows across from each other, like this:

ABC

FED

We have pairs AF, BE, and CD Now we rotate:

.AB.

F..C

.ED.

Now we have pairs AE, BD, and FC (F and C are on the ends of the rows) Rotate again:

FAB

EDC

Now we have pairs FE, AD, and BC Rotate again:

.FA.

E..B

.DC.

Now we have pairs FD and AC (E and B have already met, like I said it's not perfect) Keep rotating until you get to this:

DEF

CBA

And if I thought this through right each letter will have paired up with every other letter. I'm not sure how if it will work with an odd number of students though.

Answer 4

Here's the pseudocode for Vlion's answer above. This isn't the fastest way to do it but it's an illustration of the concept (thanks Vlion!)

// create all the edges
for i := 1 to number_of_students - 1
  for j := i + 1 to number_of_students
    edges.add(new Edge(i,j))

// select all groups from the edges
for x := 1 to number_of_students - 1
  used_nodes.clear
  group.clear

  for y := 1 to number_of_students div 2
    do
      current_edge = edges.get_next
    while (current_edge.n1 not in used_nodes) and
          (current_edge.n2 not in used_nodes)

    used_nodes.add(current_edge.n1)
    used_nodes.add(current_edge.n2)

    group.add(current_edge)

    edges.remove(current_edge)

  groups.add(group)

Answer 5

Here is C# code which solves the question.

I've assumed that you really care about maximizing the uniqueness in student pairing, not the set of possible unique groups of student pairings.

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace Pairing
{
    class Program
    {
        static void Main(string[] args)
        {
            //switch these lines if you'd prefer a command line interface to a text file.
            var rgs = File.ReadAllLines("Roster.txt");
            //var rgs = args;

            var setPairs = new HashSet<HashSet<string>>();
            for (var ixrgs = 0; ixrgs < rgs.Length - 1; ixrgs++)
                for (var ixrgsSubset = ixrgs + 1; ixrgsSubset < rgs.Length; ixrgsSubset++)
                    setPairs.Add(new HashSet<string>(new string[] { rgs[ixrgs], rgs[ixrgsSubset] }));

            var setGroups = new HashSet<HashSet<HashSet<string>>>();
            var setUsedPairs = new HashSet<HashSet<string>>();
            while (setPairs.Count > 0)
            {
                var setPairsTmp = new HashSet<HashSet<string>>(setPairs);
                var setTmp = new HashSet<HashSet<string>>();
                var setUsedVariables = new HashSet<string>();

                while (setPairsTmp.Count > 0)
                {
                    //give me the first element
                    var pair = setPairsTmp.First<HashSet<string>>();
                    //store it
                    setTmp.Add(pair);
                    //add it to our set of used variables
                    setUsedVariables.UnionWith(pair);
                    //remove it from our set of available pairs.
                    setPairsTmp.RemoveWhere(set => set.Intersect<string>    (setUsedVariables).Count<string>() != 0);

                    //remove its implicated deadlocks from our set of available pairs
                    //(this step is both gross, and key. Without it, failure potential arises.)
                        var s1 = new HashSet<string>();
                        var s2 = new HashSet<string>();
                        //get the set of variables paired with the first:
                        var rgPair = pair.ToArray<string>();
                        foreach (var set in setUsedPairs)
                        {
                            if (set.Contains(rgPair[0]))
                                s1.UnionWith(set);
                            if(set.Contains(rgPair[1]))
                                s2.UnionWith(set);
                        }
                        s1.IntersectWith(s2);
                        //enumerate the pairs created by the deadlocking pairs, remove them from our available selections.
                        var rgsTmp = s1.ToArray<string>();
                        for (var ixrgs = 0; ixrgs < rgsTmp.Length - 1; ixrgs++)
                            for (var ixrgsSubset = ixrgs + 1; ixrgsSubset < rgsTmp.Length; ixrgsSubset++)
                                setPairsTmp.RemoveWhere(set => set.Contains(rgsTmp[ixrgs]) && set.Contains(rgsTmp[ixrgsSubset]));
                }
                setPairs.ExceptWith(setTmp);
                setGroups.Add(setTmp);
                setUsedPairs.UnionWith(setTmp);
            }
            //at this point, setGroups contains the set of unique group combinations.
            //the non-maximally sized groups indicate unique sets that could form provided that
            //all other students are in redundant sets.

            var enumerableGroups = setGroups.OrderByDescending<HashSet<HashSet<string>>, int>(set => set.Count);
            //Sanity Check:
            foreach (var group in enumerableGroups)
            {
                Console.Write("{");
                foreach (var pair in group)
                    Console.Write(string.Format(@"[{0},{1}]", pair.ToArray<string>()));
                Console.WriteLine("}");
            }
        }
    }
}

Answer 6

The algorithm you are asking for seems more or less the same as the algorithm for preparing schedules for round-robin tournaments. The details can be found in this Wikipedia article. You can also use generators lying around on the web for a quick tryout. One of them can be found here.