General Algorithm - Seating Plan

Tetsujin

Tetsujin

Tetsujin

Associate
Joined
23 Oct 2002
Posts
1,525
Location
That London, née Brighton
So, an old friend of mine has come to me with a problem. He's planning a networking event in his business sector, with a bit of a twist - the seating arrangements are switched around every X minutes, speed dating style, to maximise everyone's exposure to everyone else. He's asked me to figure out the optimal algo so that by the end, all N people end up having gotten on a table with all N-1 other people. Now his sector happens to be education and he's put this to several maths teachers and got nothing useful back, so it may be a tall order, but still.

The most obvious "shift everyone left by 1" doesn't work as there's multiple people per table. Total of 10 tables with 8 seats per table, in fact. And each of these 80 people should have had a chance to talk to as many of the other 79, with as little duplication (i.e. sitting with the same person multiple times), as possible. Now due to cross-pollenation of ideas ("oh yeah that guy was talking about something similar") not everyone will need to physically sit with everyone else for best results, but a reasonable percentage (80%? each person sat with 60-65 others?) would be good. It's also obvious that minimally 12 'rounds' are needed (79 people to see / 7 people at a table = 11.3 which ~ 12) for the maximal case.

Anyone know of a general purpose algo for this sort of thing?
 
im completely just thinking of the top of my head but maybe use a matrix

So 80x80 matix, each row represents one person i.e. row value = person ID, then in the columns we have 0 or 1 representing whether they've sat with that person or not.

Write a recursive function that then picks a person and works out who they have or haven't sat with by looking at the column from that matrix, generate a list of people they havent sat with and randomly select those people and assign them a table between 1 - 10.

Again this is not a particularly great algorithm i would say and i may be talking complete rubbish because I have literally come up with this on the spot, but just throwing an idea out there.

Gd luck either way
 
oo didnt realise you were planning on doing it in excel :-P I was just thinking you were tlkin about using a programming language, sooo php should be all gd i imagine :-P
 
Yeah I'm not sure why but my initial thought was to try and hack through it manually, but then I did get the phonecall at half 9 this morning while still in bed so... stupid not-awake-enough-ness causing me to run up the wrong path!
 
I'm taking a wild stab in the dark here as my maths isn't that good, but if you assign everyone a number and then create a permutation matrix of 80 rows and columns.

If you multiply the vector of numbers with the permutation matrix then you'll get a re-ordering of that vector. You can then fill each chair in turn in the order they're in the permuted vector, rinse and repeat.

I *think* since the matrix of "who has seen everyone else" is symmetric, in n/2 swaps you can have everyone seeing everyone else but one person. So in 40 swaps everyone will have 78 people but never met the 79th person. (You are the 80th person, so you always meet yourself.) The other 40 swaps before the permutation matrix returns you to where you started are all concerned with getting people to see that last person and duplicate a lot of other people seeing each other unnecessarily. The full 80 swaps will get you everyone seeing everyone else as evenly as possible, but I'm guessing you don't have time to do a full permutation. Drop the number of permutations even more (say, only do 20 swaps) and you should still have a decent spread I *think*, but I don't know the exact statistics and honestly wouldn't know how to work it out. All of this is based on my intuition that this is just a permutation problem with some extra kinks in it. I couldn't prove it to save my life. If you can get the Permutation Matrix then you shouldn't have too much problem coding it up and it'll take seconds to calculate the seating orders so you should be able to just experiment and find out.

To get the Permutation Matrix in the first place:
Solving the latin square problem (sudoko where none of the squares come pre-filled) and only keeping the 1's to represent your permutation matrix swaps will get you there, but it's computationally very expensive, I'm sure some research on your part will get you a faster method.
 
No problem. To be honest, I think computing a 10 * 8 permutation matrix will be rather difficult and time consuming. Alternatively you could permute them the old fashioned way, but be aware that the algorithm for finding permutation has n! in it, which at 80! is quite a lot. More than 2^63, so your PC won't handle it without some kind of BigInteger class.
 
Give everyone a number, once you have generated each seating plan, store a tuple of [person],[sitting_with_person] in a db, then for each person you can do a select where not in (tuples), therefore deriving a new unique tuple (i.e. ensuring that person has not sat with that other person before).

Does that make sense?
 
You must log in or register to reply here.
Back
Top Bottom