classroom constraint satisfaction problem

[Steven Bethard]

Carl Banks wrote:
> Steven Bethard wrote:
>> Basically, I want to build groups of two teachers and four students such
>> that [1]:
>>
>> * Students are assigned to exactly one group
>> * Teachers are assigned to approximately the same number of groups
>> * Students are not in groups with their homeroom teachers
>> * Students in each group are from four different homerooms
>>
>> So given teachers A, B, C, D, E and F and their corresponding students
>> A1, A2, ... F3, F4, here's a good grouping:
>>
>> A, B:   C1, D1, E1, F1
>> B, C:   A1, D2, E2, F2
>> C, D:   A2, B1, E3, F3
>> D, E:   A3, B2, C2, F4
>> E, F:   A4, B3, C3, D3
>> F, A:   B4, C4, D4, E4
> 
> [snip]
> 
>> [1] There are actually two other constraints that I omitted:
>>
>> * Some teachers cannot be placed in the same group, e.g. I might know
>> that A cannot work with B or that E cannot work with F.
>>
>> * If you create a graph out of the teacher pairs from all the groups,
>> the graph should not be disconnected.  That is, the following grouping
>> is bad because the teachers are disconnected:
> 
> I would do it in two steps.
> 
> Step 1: Generate a graph of all teachers, such that there is one
> connection for every four students, and each teacher has approximately
> equal number of connections.  A simple, approximate way to do this
> would be to generate random subsets of two teachers until you have
> enough connections (though that won't work well if you have a lot of
> teachers that can't work together, which wouldn't be surprising).  I'm
> sure graph theory has some algorithms to do this if you need more
> exactitude.
> 
> Step 2: Assign students from appropriate homerooms to each connection.
> The following simple algorithm is probably satisfactory: for each
> connection between teachers, choose a random subset of four homerooms
> not governed by those teachers to form a group.  Assign a random
> student from each homeroom.  Once every student from a homeroom has
> been been assigned, remove that homeroom from the set of available
> homerooms.  With this method, you might have some connections at the
> end without enough remaining homerooms; just go fishing for a suitable
> switch among students already assigned.  Or, work out a way to make
> sure you don't exhaust too many homerooms.  Perhaps there is a known
> algorithm for doing this.

For what it's worth, I went basically this route.  My code does 
something like:

(1) Generate all pairs of teachers

(2) Remove any pairs of teachers in conflict

(3) Create a list for teacher pairs

(4) Randomly select a teacher pair and add it to the list

(5) If any teachers are at their max number of groups, remove all pairs
     that include them from the pairs we are randomly selecting from

(6) If we have not selected a teacher pair for each group, goto (4)

(7) If the resulting graph is disconnected, try again from step (3)

(8) We now have one pair of teachers for each group

(8) Randomly select four other teachers' homerooms for each group

(9) Randomly pop a student off of each homeroom and add it to the group

(10) If a homeroom becomes empty, remove it from the homerooms we are
      randomly selecting from.

(11) If at any point we run out of students, try again from step (3)

(12) Eventually, we have assigned people to all teacher-student groups

This seems to work pretty quickly, and doesn't have much trouble finding 
solutions to the datasets I've tried it on.

Thanks for your help!

Steve