[Edu-sig] Roommate Matching Algorithm

[Jay Bloodworth]

Hi.  This is perhaps a bit bit off topic as it is not related to using
python for direct teaching and learning, but it is about using python
for an actual project in an actual school.

I'd like suggestions for an algorithm for "optimally" placing kids in
rooming groups for a field study.  The data I have for each student is
an unordered list of four people he'd like to room with.  I don't have a
firm definition for "optimal" (open to suggestions), but I'm thinking of
something like satisfying the following conditions, in order of
priority.

1) Every student rooms with at least one person they requested.
2) The preference graphs for individual rooming groups are as complete
as possible, i.e. groups that all mutually request is other should be
identified by the algorithm where such exist.

I have found several descriptions of matching algorithms on the web, but
most have them have been for simply pairing items, not creating larger
groups.  Also, most assume we have rankings of all the other set
members, not just a few identified as preferred.

Suggestions?  I have a couple of ideas, but I don't want to reinvent the
wheel.  I can be pretty generous with the definition of optimal -
condition 1) is the only thing that is really mandatory.  Lest anyone
worry that automating this process is too impersonal, we will certainly
do a sanity check on any list generated based on our knowledge of the
kids, and jigger it where we deem it sensible.

Thanks,
Jay