[Edu-sig] Roommate Matching Algorithm

[Andre Roberge]

Could you provide a sample data set?

André

On 1/26/07, Jay Bloodworth <jbloodworth at sc.rr.com> wrote:
> 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
>
> _______________________________________________
> Edu-sig mailing list
> Edu-sig at python.org
> http://mail.python.org/mailman/listinfo/edu-sig
>