I'm getting married soon and am busy with the seating plan, and am running into the usual issues of who sits where: X and Y must sit together, but A and B cannot stand each other etc.
The numbers I'm dealing with aren't huge (so the manual option will work just fine), but being of the geeky persuasion, I was wondering if there was any software available to do this for me?
Failing an exact match, what should I look for (the problem space, books, reference code) to tweak for my purposes?
I expect this isn't a great answer, but you could research flocking behavior
If you take away the random jitters at each step, the flock eventually settles where each member has found its optimum position in relation to the rest of the group.
Try modeling this using GLPK. Integer linear programming is amenable to introducing constraints into graph-based problems with multiple possible outcomes.
I used a program a while ago that would fit this perfectly... it was a Java App, you could define rules, and it would create test cases that satisfied the rules. The file extension was .als
fact GateRules { all g:Gate | one g.loc // Gates have 1 Location
I'll keep wracking my brain for the program name.
EDIT: It was Alloy Now that I think about it, it may not be ideal - the notion of "seats in a fixed configuration" would be a little difficult to model. I used it differently: defining rules (an airport gate is in one location, only one plane is on a runway), and testing pre and post conditions for functions (after I land a plane, can i even have more than one plane on a runway?).
http://www.perfecttableplan.com/
I believe this is from a guy that usually posts at Joel On Software.
Never tried it though. Hope it helps.
My personal favorite is to not assign seating: allow folks to sit wherever they want.
That might lead to [un]intentional cliquishness, but it means you're not having to worry about it.
I am the developer of PerfectTablePlan. I post here as well as Joel's Business of Software . ;0)
Combinatorial problems, such as seat assignment, are quite nasty algorithmically. NP-hard in fact. The number of ways to seat 60 guests in 60 seats is 60! (60 factorial) and that is more than the number of atoms in the known universe.
PerfectTablePlan allows you to specify that A must sit next to B, but nowhere near C. It uses a genetic algorithm to automatically the assign seats. This works pretty well in practice - it will usually find a decent solution for 100 guests in a few seconds. You might need to make a coffee for 1000+ guests. In practice some drag and drop fine-tuning is also usually required to cope with the vagaries of local customs and family politics (Uncle Bob is a bit deaf, we had better put him nearer the top table).
You can find out a bit more about the genetic algorithm here.
Ps/ The automatic seat assignment is only a small part of creating a good seating plan. See the PerfectTablePlan tour and the tips page for more details.
This sounds like a constraint satisfaction problem. You should probably check out logic programming systems that are also equipped with constraints-solvers. They're usually like prolog, only they are actually declarative for problems that are soluble by their solvers.
Hopefully there is one that has an easy interface from your favourite language, to get the data in and out.
Hi... could you give me some information about an algorithm to search te best seat available on a concert hall. i've been looking for that.. months and months and i finally got something similar but not exactly what i looking for since there's a lot of difference between a wedding seating chart and a for example a concert hall, a baseball stadium... how can apply genetic algorithms on this???. For a reference of my problem check one of the popular ticketing pages: tickets.com , mlb.com... THANKS