8

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)

  1. Why do I get a different number of generated assignments every time I run the program? The data set isn't changing between runs.
  2. 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?
  3. 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.

Improve this question
2
  • honestly you might try mathematics.se, this is some pretty complex math. Commented Dec 20, 2012 at 16:50
  • @MatthewD Your question is fine here, and since you already found an answer I don't see why we should migrate it. If you want a more mathematical answer, you can re-post it on Mathematics, but please make sure to make the question suitable for the site (read their FAQ for more), don't just copy paste it. Generally we don't like having the same (or very similar versions) question on multiple sites, but yours seems to be on topic for both sites. it could work on Maths with minimal changes. Commented Dec 20, 2012 at 20:04

1 Answer 1

Reset to default
4

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...

  1. 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 designed instead of a bug.

  2. 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.

  3. 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.

Improve this answer
4
  • Thank you for the links! :) (See my edit for how I'm generating assignments) Commented Dec 20, 2012 at 17:05
  • @MatthewD - looks like the randomness you are seeing / asking about is intentional and expected. Without your other constraints, there are 60! permutations of the student roster you're using to populate the tables. Your other constraints will cut down on the maximum number of permutations, but that's a fairly large starting point. Commented Dec 20, 2012 at 17:18
  • This link you gave suggested "pick table with least undesirable members." I did that, and now it is consistently generating solutions no matter how many weeks I tell it to generate. I'm going to play with how I implemented it, as well as look at how many times it fails to find a perfect match, but so far, it looks like it is working. Thank you very much! Commented Dec 20, 2012 at 19:12
  • One of the answers in the SO questions stated that it's an NP hard problem, which is polite for "may not be (completely) solvable." If that's what you end up running into then you can just cheat the problem so it will solve, tell the counselor about it, and move forward. Commented Dec 20, 2012 at 19:59

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.