homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightcombinatorics

Seating chart

This calculator tries to find seating chart combinations taking into account preferences of students.

One of the site visitors formulated the following task:
"I am a teacher and I ask my students to pick two people they would like to sit by. When I do this I have to put all the names and combinations down on paper and go through and organize them. I was wondering if there was some way that I could input names and choices and it would give me a list of combinations based on there choices. Some kids are more popular than others and their names show up frequently. I also have students that nobody wants to sit by. It is a tough decision. I change my seating chart frequently and this would be a great time saver."

It is rather interesting, because you can't solve it with brute force by enumerating all combinations. Even for 14 students number of combinations is quite overwhelming - 9166452815*6 = 681,080,400.
To solve this, I decided to code genetic algorithm. As it is with all heuristics algorithms, it does not necessarily produce optimal solution, but in most cases solution can be good enough for practical reasons.

Of course, this task can be solved with other algorithms from graph theory, but I just wanted to practice with genetic algorithms. So, calculator below creates seats arrangement using genetic algorithm. You can play with number of "generations" to reach the better solution as well as with "population" size. Default values look to be good enough for 14 students.

PLANETCALC, Seating chart

Seating chart

Students preferences

Student nameSeating preferences
Items per page:

Digits after the decimal point: 2
Chart efficiency
 
Seating chart

P.S. Later I'm also going to cover this task with graph algorithm.

Comments