Assigning Classes

[Pierre M]

Feeling less lazy now. If you decided to still implement something
yourself, here is a non-optimal algorithm whose first aim is to assign all
students, so that teachers don't have to do it manually. It should reach a
first (suboptimal) solution very fast, and enable further optimization if
you want.

Put all students in their 5th and 4th choice (over-filling the classes).
Then, get rid of students in Over-Full Classes (OFC), by assigning them to
other classes that they prefer: for each OFC, take the students who chose
it as 5th choice, and put them in their 3rd choice instead if it is not
full.

When you have done this for all OFCs, keep on doing the same: take the
"less happy" students of an OFC, and assign them to their 2nd choice if
possible. And then a round of 1st choices.

Hopefully, you'll end up in a (suboptimal) situation where all students
have some of their choice fulfilled, and there are no more OFCs. The first
part of the contract is fulfilled: teachers won't have to do anything
manually.

>From there you can optimize:
    - move each student from one class to a better class, if there are
places available in that class (it's still very simple and fast);
    - do beneficial permutations. That can get more complex, as sometimes
you will "push in better classes" several students successively, until one
gets an empty place somewhere.

In terms of implementation, i'd say each class has 5 lists of students, to
quickly choose which students to move first.

And a 3 step algorithm:

fill_classes_naively();
get_rid_of_OFCs();
optimize();

In get_rid_of_OFCs(), each OFC tell its most unhappy students to check if
their "slightly better" class has a place for them.

That's it. Critics and comment very welcome.