There are around 60 students at the boarding school I work for. The counselor asked my colleague and me to come up with a better way to come up with seating arrangements for dinner than by hand. He would like assignments for the rest of the school year. He also asked us to try to solve some of the issues he has hearing about from students and faculty.
- Most of the students are not from the US, so when they are surrounded by people of the same nationality (i.e., at the dinner table), they speak the language they are fluent in, instead of practicing English,
- Complaints are made when students have sat at a certain table "too many" times overall,
- or if they sit at the same table more than twice in a row,
- and some of the students do not get along, so they cannot sit together.
At run time, the program is supplied with:
- A set of people,
- A set of tables, and
- Each table has a different number of seats (repetition is allowed)
The size of both sets, and the size of each table does not change between each assignment.
I am using 18 people of different nationalities, and 4 tables of size 3 through 6, inclusive. I picked numbers that I thought made sense for that data set:
- No more than 3 people of the same nationality can sit together at a time
- No person can sit at a table more than 4 times
I have run the generator around 15 times without changing the input data. Each time, it comes with anywhere from 6 to 12 "weeks" of assignments.
(least to most important)
- Why do I get a different number of generated assignments every time I run the program? The data set isn't changing between runs.
- How do I find the...
- minimum number of people of the same nationality that can sit at a given table,
- minimum number of overall times they sit at a given table, all while
- maximizing the number of generated assignments?
- How do I guarantee that these actually are the correct numbers?
Each time I generate a new assignment, I call
Collections.shuffle(List) on the list of people to randomize their order. I then pass the list of tables and people to a backtracking method based off of kapilid's eight queens implementation on github to assign people to tables.