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

This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/5768/. Also, please do not modify any references to the original work (if any) contained in this content.
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 - 91×66×45×28×15×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.
P.S. Later I'm also going to cover this task with graph algorithm.
Comments