Seating arrangements for a school class.



  • Disclaimer: This may offend some people's sensibilities for some reason. If you feel offended, I'm sorry, but I will carry on regardless.

    I sort of have to rearrange the seating of one of my school classes. Instead of shuffling the whole class around randomly, I wanted to give it some structure. Thus I used an idea from a fellow teacher:
    Each pupil gets to choose two names:
    One person he/she likes and wants to be seated next to and one person he/she dislikes and does not want to be seated next to. They can also indicated whether they want to sit in front (or if they don't care). All three options are ... optional.

    I myself want to forbid certain seating arrangements - like: this pupil should not be seated next to that one, due to them both being disruptive when sitting next to each other. This is not optional.

    That would be the data for each pupil. The data for the seats is easy as well: Each seat would get an index number and two variables indicating whether they have a right or left neighbour and, in case they do, which index number that is.

    My first attempt was to simply brute-force it. Recursive algorithm, iterate through each seating arrangement and giving it a score (like: Two points for fulfilling a "like" arrangement, one point for avoiding a "dislike" arrangement, one point for fulfilling a "front" arrangement and setting the score to zero when not fulfilling my blocking arrangement), and them simply picking the one with the highest score.

    Well, that may work well for a class with only 10 pupils, but mine has 28.
    When you do the math, that's the factorial of 28. Which is the quite small number of 3. Which 29 following zeroes.

    Anyone have an idea of how to reduce the complexity or approximate some results in order to achieve a more sane number of combinations to be calculated?

    I'm using C# - so please no language constructs not in use by that language :)

    I myself was thinking of reducing the 28 seats to 14 by dividing the class into "fitting pairs" first - which would reduce the combinations to 14! - still a large number but something my computer can crunch through before the heat death of the universe

    .

  • Discourse touched me in a no-no place

    @Rhywden said:

    Anyone have an idea of how to reduce the complexity or approximate some results in order to achieve a more sane number of combinations to be calculated?
    Use common sense/intuition instead of a computer program. It'll take less time and effort in the long run.





    How old (mentally/physically) are the students concerned? Presuming they exist that is.



  • @PJH said:

    Use common sense/intuition instead of a computer program. It'll take less time and effort in the long run.

    And here I thought this was a forum for coding related questions.



  • @Rhywden said:

    @PJH said:
    Use common sense/intuition instead of a computer program. It'll take less time and effort in the long run.

    And here I thought this was a forum for coding related questions.

    It is, the answer is "it's faster not to do it."


  • There's some vagueness in your requirements. Does sitting 'next to' mean the seat immediately to the right or left, do you count forward and back, what about diagonals? Is 'sitting in the front' on the first row? How many desks in each row?

    I'd start by placing the students who want to be in the front. Based solely on their requirements, the problem may have no solution and then you can avoid wasting further CPU cycles until you adjust the requirements to make the problem solveable

    Agreed that human intuition and common sense might be a better approach than an algorithm, but at least you can be sure the algorithm is fair. Of course most days I prefer neat Project Euler problems to messy human relations problems.


  • ♿ (Parody)

    This sounds like constraint programming could be a reasonable approach. It's often used in situations where there are very large solution spaces (which yours really isn't). With only 28 variables, you could probably even do this using the built-in Excel solver.

    Basically, you'll need to come up with a set of equations to represent the seating arrangements. Probably, you'd want to abstract the students into an object, and have a variable that represents where they're seated. Then you'd start adding constraints based on the student input and your stuff. Ideally, you'll also have an objective function to be able to compare different solutions.

    Then you start assigning seats, and propagate the results of each decision through your constraints to limit the values of the other variables. If you use a library, it will probably have some canned functions for doing just this. There may be options for searching the solution space, or you might customize the search itself, instead of just using the canned functions.

    Looking around, I didn't see a lot of .Net libraries for this sort of thing (though I admit I didn't look very hard). You might take a look at Google's OR-Tools. I've never used them, but they appear to have a .Net version.

    In this case, though, the most efficient thing will probably be to just do this manually. If you need a quick answer, that's what I'd do. But solving it programatically will be more fun, and I'd probably still do it, even after I'd already rearranged the students.



  • @boomzilla said:


    In this case, though, the most efficient thing will probably be to just do this manually. If you need a quick answer, that's what I'd do. But solving it programatically will be more fun, and I'd probably still do it, even after I'd already rearranged the students.

    Thanks for your insight. And yes, manually might be faster. Then again, this is something I simply want to do to see if I can.

    A motivation certain previous posters don't seem to understand.



  • Write a genetic algorithm or use this tool which is free for up to thirty people: http://www.perfecttableplan.com/html/dinner-party-seating.html

     



  • @Rhywden said:

    @boomzilla said:


    In this case, though, the most efficient thing will probably be to just do this manually. If you need a quick answer, that's what I'd do. But solving it programatically will be more fun, and I'd probably still do it, even after I'd already rearranged the students.

    Thanks for your insight. And yes, manually might be faster. Then again, this is something I simply want to do to see if I can.

    A motivation certain previous posters don't seem to understand.

    This is a linear methods problem (a.k.a. resource scheduling, linear flows, or network flows). This is actually a well defined special class of problem ... I just can't recall the name of it.

    You have resources (seats) and requirements (students). The seats have distance relationships between each other in xy space (assume the only valid paths are of unit length and are left/right, front/back). You have distance relationship requirements (e.g. the geometric (not path) distance between two resources must be greater than or equal to 2 for the bad pairs or the distance must be 1 for good pairs) from here you place the students along the Rows and the seats as the columns and build a 1-to-1 map for their positions and compute to see if all of the restrictions are satisfied. If not, you pick a constraint that is not satisfied and perform a seat swap to satisfy the constraint and then recompute. Rehash until you find a solution or decide your solution space is unattainable (you can usually see this when the only next hop available returns you to a known state of non-solution). Then you would relax your constraints (probably by allowing the distance for the good pairs to be less than 2) and repeat.

    If I remember the name or remember to look it up when I go home tonight, I'll let you know.


Log in to reply