Background:
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.
Constraints:
- 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.
Input:
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.
Tests:
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
Results:
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.
Questions:
(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?
Edit:
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.
2
Update:
I realized I didn’t directly answer your questions. I suppose it helps to read all of the question before firing off an answer…
-
You don’t specify what algorithm you’re using to generate the seating arrangements. Presumably there is some element of variability / randomness in order to create different assignments for the duration of the term. That randomness is most likely the reason why you’re getting differing results on each run. I’d mark that as
working as designedinstead of a bug. -
a. You don’t specify the algorithm, so we don’t really know. We also don’t know the counts for each nationality. By simple logic, 0 or 1 would be the absolute minimum at a table, but I suspect that’s not very helpful to you. Ultimately it depends upon the number of each nationality and how they populate the other tables.
b. Run your program, throw the results in a database or spreadsheet and have it count for you. Or alter the program to keep track of those things.
c. The answer here is going to be dependent upon the number of each nationality and the other constraints you supplied. Table size will also affect it. The answer to this portion is really just a multiplication of the number of potential permutations. Fortunately (for me) this is a site about programming, not statistics. -
You have two issues to contend with here. First is validating that your constraints accurately reflect the reality of the situation. Talk to the counselor to verify your constraints are correct. Second is verifying your results fulfill your constraints. Write some methods that check the returned seating charts for the constraints you provided. And / or manually inspect the charts to verify they are okay.
This SO Question has a similar question and suggests that this is equivalent to the bin packing problem or the knapsack problem
This SO Question Seat guests based on prioritized parameters seems to address exactly what you’re looking for.
This SO Question discusses problems the author had in solving this problem using the bin-packing algorithm. I’d suggest reading the answers to get a better insight in how to work around them.
And for the obligatory xkcd reference, here’s a link from their forums discussing seating plan optimization and using a modified genetic algorithm to solve the problem.
If this is a real scenario, then best of luck. And if this is just homework then you’ve got more than enough material to move you forward with.
4