Seat guests based on prioritized parameters

Question

The following data model represents tables with seats and guests, in an application that lets a user create tables and seats, visually using HTML5.

// The data model
var data = {
    guests: [], // id, name, tags
    tables: [], // id, seats
    seats: [], // id, guest
    tags: [] // id, name
};

The guests have tags (kind of categories) attached to them. These tags can be prioritized and set to work as "grouping" or "ungrouping" parameters. The user then clicks "Seat", and the guests are seated (seemingly randomly), while the prioritized parameters are respected.

Full-blown example: http://jsfiddle.net/kBp49/2/ (look for "SOLUTION GOES HERE" in JS panel)

The question is: How do I implement a function that seats the guests to the tables, while taking into consideration that some guests should be seated next to each other and others should be seated apart from each other in order to create one of the best seaating configurations? The number of guests can exceed 1000 but not 2000.

Real life example, to clarify the problem

Let's say we have 3 tables. They have 4 seats each. Let's also say that we have 9 guests to fill these tables with. They are as follows:

1. Guest 1, Jewish, from US
2. Guest 2, Jewish, from UK
3. Guest 3, Christian, from US
4. Guest 4, Christian, from UK
5. Guest 5, Christian, from Sweden
6. Guest 6, Atheist, from UK
7. Guest 7, Atheist, from Sweden
8. Guest 8, Muslim, from Saudi Arabia
9. Guest 9, Muslim, from UK

Now, the user prioritizes the parameters like this. First is most important.

1. I want those with the same religion to sit apart from each other
2. I want those with the same geographical location to sit next to each other

This is OK:

1. Table 1: Guests: 1, 3, 7, 8
2. Table 2: Guests: 2, 4, 6, 9
3. Table 3: Guests: 5

Update One solution could be the Minimax algorithm. It would calculate a score for each possibility and present the best found solution (found after, say 10 seconds of calculation). The algorithm is what I need help with, the implementation itself will of course require decisions that only I can make.

Answer 1

There is no best answer to this question, because there is no best seating arrangement - in fact I would argue that the arrangement that you say is OK is probably pretty bad - if you are forced to use three tables, and you can seat at max 4 per table, you should probably seat three at each table so that no-one ends up sitting alone. That is nit-picking, however, and avoids the basis of the question.

There are a few algorithms that I can envision.

First, you can treat each "tag" as a dimension in an N-dimensional space (this sounds more complicated than it is). For example in the region dimension, you can assign each country an integer value, and the dimension for your regional space will have each of these integers as potential values. Then, place each guest as a point in this N-dimensional space, and select for each table those guests who are closest together in that space. You can support priorities by ignoring some features when building the space - i.e. if you don't want grouping by religion, don't include religion while building the space, or if you actively want separation between people with 'like'-religion, you can modify your distance calculation to have an inverse relationship in that dimension. This algorithm could have good performance depending on the number of features (i.e. dimensions), and the number of points - this is essentially how they create recommendation engines.

If you wanted something simple but slow, you could use a brute force algorithm: i.e. for each guest, look at each table that has members on it, if these members are not desirable given your priorities, seat at a fresh table. If no fresh tables exist, pick table with least undesirable members. This is probably as simple as you can go!

Finally, you might be able to pre-process your guests, and count: how many are from region x, how many are from religion y, ... then, once you have these statistics, you can create the tables (depending on priority) like: the canada table, the UK table, ..., and then seat the guests at any table that matches their description. Weather this is feasible depends on the input set.

I hope this helps, and gives you some ideas about how to solve this problem :)