4

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?

jjnguy
  • 136,852
  • 53
  • 295
  • 323
nwahmaet
  • 3,589
  • 3
  • 28
  • 35

7 Answers7

12

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.

Andy Brice
  • 2,297
  • 1
  • 21
  • 28
  • Isn't this a discrete constraint satisfaction problem? Surely a constraint-programming solver could do this quite easily? – Marcin Oct 08 '08 at 22:31
  • Which incidentally isn't to do down the features of your product that would be a pain with a home-brew solution - like anything that isn't a bunch of text. – Marcin Oct 08 '08 at 22:35
  • If you have 100 guests and each has 5 preferences of other guests he wants to sit near to or far from, could a constraint-programming solve that in a few seconds on a standard desktop PC? Is it financially viable to buy or write a constraint-programming solver for a $35 product? – Andy Brice Oct 08 '08 at 22:41
  • This articles shows an MINLP solver taking 36 hours to solve an 107 guest problem and that is assigning tables rather than seats: http://www.improbable.com/news/2012/Optimal-seating-chart.pdf – Andy Brice Nov 11 '12 at 21:30
6

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.

Antonio Louro
  • 528
  • 1
  • 5
  • 14
1

Try modeling this using GLPK. Integer linear programming is amenable to introducing constraints into graph-based problems with multiple possible outcomes.

Robert Elwell
  • 6,598
  • 1
  • 28
  • 32
1

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.

warren
  • 32,620
  • 21
  • 85
  • 124
  • @nwahmeat: because the invitor usually can group people with common interests more efficiently than the same people alone -- especially if they don't know each other – David Schmitt Oct 08 '08 at 19:03
  • 84% of guests prefer assigned seats, see: http://www.prweb.com/releases/2006/2/prweb344508.htm . ;0) – Andy Brice Oct 08 '08 at 22:43
0

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.

Geoff
  • 9,340
  • 7
  • 38
  • 48
0

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

Jan van Haarst
  • 3
  • 2
Tom Ritter
  • 99,986
  • 30
  • 138
  • 174
0

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.

Marcin
  • 48,559
  • 18
  • 128
  • 201