Seating chart

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.

Seating chart



Students preferences

	Student name	Seating preferences
			

Population size

Number of generations

Calculation precision

Digits after the decimal point: 2

Calculate

Chart efficiency

 

The file is very large. Browser slowdown may occur during loading and creation.

Download 

 Link  Save  Widget

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