Seat Guests Based On Prioritized Parameters

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 = {

Solution 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 :)