Generating student seating charts?

July 25, 2006 9:59 AM

Dear Mostly-Random-Student-Seating-Filter: Can you think of a tool (or a clever method) for regularly generating new seating assignments for students sitting at tables? Other criteria inside...

The seating assignments need to change every 2 weeks, there needs to be a mostly even mix of male/female at each table, and each table needs to have a mix of different grade levels at it. (I found a freeware program called "Seatem" but the only download I was able to get at seems to be corrupted or something - it throws an error when you start it up.) Does anyone know of another similar program, or a clever way to generate seating, given these limitations? (I'm asking for a friend, and I may not be able to get much more info than stated here.)

posted by chr1sb0y to education (10 comments total)

Generate a random permutation constrained by your constraints on gender and grade level mix. Simplest way might be to generate the initial; permutation, subject it to a fitness function that checks for a close enough match to your ideal mix, and keep generating until it passes the test.

In C++, use the STL next_permutation and write a fitness function that "walks" each "table" (offset into permuted array) calculating sums of gender and grade level by calling STL function for_each with a summing predicate functor.
posted by orthogonality at 10:13 AM on July 25, 2006

The simplest way may be a Monte Carlo method.

1. Put Student 1 at random table
2. Put Student 2 at random weighted table
3. Repeat 2 until done.

Calculate the weights for each table on each iteration based on:
1. Specific Gender more likely to get placed at tables with fewest number of people with that same Gender.
2. Grade levels more likely to get placed at tables with fewest number of people at that same grade level.

Its a simple program in any language. You just have to play with the weights until you get results that, by eyeball inspection, look good enough.
posted by vacapinta at 10:19 AM on July 25, 2006

Or have "slots". For each table, choose one from "Male, Grade N", "Female, Grade N", "Male, Grade N+1" and so on. Or choose one from "Grade N" and then reject the choice if you already have more than half a table's worth of that gender. Something along those lines.

Extending that idea, choose randomly one at a time; if the table you're adding that person to already has more than enough men/women/people of a particular grade, then choose again.
posted by spaceman_spiff at 10:22 AM on July 25, 2006

spaceman_spiff writes "choose randomly one at a time; if the table you're adding that person to already has more than enough men/women/people of a particular grade, then choose again."


The difficulty with this is that you could get a random sequence of arbitrary length that assigns to the "wrong" (already has enough people of that type) table, so you keep going back and trying again. A the tables fill up, the greater the chance of rejection, so toward the tail end of the program, the number of tries increases (asymptotically?). also, if your initial random assignments are such that they pass the fitness test but that you can't reach a solution, you'll endlessly generate random assignments that you have to reject -- you can't "go back" and reassign the already assigned to escape the cul-de-sac.

By permutating, so long as even one of the permeations passes your fitness test, you know you'll eventually reach that permutation in finite time, because you have a finite number of permutations to check.
posted by orthogonality at 10:32 AM on July 25, 2006

Ha - thanks for the answers so far. I should have added that I really am not interested in algorithms for programming this. (Well, I DO find the algorithms interesting, but they aren't going to help my friend in this situation, unless someone wants to write an app using one of them.) The best solution would be a cheap/free program or a clever and simple method that could be used by multiple teachers in a school setting.
posted by chr1sb0y at 11:17 AM on July 25, 2006

Clever method:
Depending on the number of tables it would be pretty easy to:

1. Have each student write their name on a token and deposit it into one of multiple boxes. The boxes are divided by sex and age. IE: 1st grade male, 1st grade female, 2nd grade male ...
2. Starting with table one sequentially select one token from each box until the table is full then move onto table two.
3. Extra entropy can be introduced by mixing up the order of the boxes that lots are drawn from every week. Or you could roll an appropriately sized (4,6,8,10,12) die to determine the next box to draw tokens from.

posted by Mitheral at 11:29 AM on July 25, 2006

Perfect Table Plan does exactly what you want. They have a free trial.
posted by davar at 11:35 AM on July 25, 2006

a) Get all the students to write their name on the face of a playing card.
b) On the back of each card, write the grade and gender. Maybe use colors to make step d easier.
c) Shuffle then deal out one card to each place face down.
d) (optional) Rearrange a few cards to even out any huge imbalances.

Not an optimal solution, but probably a good enough one.
posted by yetanother at 11:54 AM on July 25, 2006

Oops - could have just said 'use Mitheral's method, but maybe simplify it'.
posted by yetanother at 11:57 AM on July 25, 2006

Ortho: yeah, I should've said, only loop a given number of times if you can't find a solution, then start from scratch. It's not "algorithmically correct", but it works for what I assume is a relatively small dataset.

That said, looks like an algorithm wasn't what the OP wanted anyway.
posted by spaceman_spiff at 12:18 PM on July 25, 2006