Steven Bethard wrote: > I'm trying to solve a constraint-satisfaction problem, and I'm having > some troubles framing my problem in such a way that it can be > efficiently solved. > > 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. Carl Banks -- http://mail.python.org/mailman/listinfo/python-list
