Honestly, I'd go with some sort of annealing-ish algorithm. Basically:
- Start with a set of rules and an initial arrangement.
- Make a random change, keeping it if it improves.
- Repeat until a solution is found. Give up after some threshold number of iterations.
Consider the following (Python). The first thing you want to do is come up with a way to measure the success of a table. Here we define a function that returns the number of bad pairings, where:
enemies: A dictionary mapping a person to the list of people they can't sit near.table: A seating arrangement in the form of a list of names going around the table. The first and last elements are adjacent seats, as it is a round table.
We'll use this for everything. Our goal is 0.
def tablePenalty (enemies, table):
penalty = 0
for k, name in enumerate(table):
p = (k + len(table) - 1) % len(table)
n = (k + 1) % len(table)
if table[p] in enemies[name]:
penalty = penalty + 1
if table[n] in enemies[name]:
penalty = penalty + 1
return penalty
So now that we have that, we can implement a really naive search, which just constantly randomly swaps people until something satisfactory is found. This takes a list of names as input, and produces a list of names in seating order as output:
def findGoodSeating1 (names):
table = names[:]
while tablePenalty(enemies, table) > 0:
i, j = random.sample(range(0, len(table)), 2)
table[i], table[j] = table[j], table[i]
return table
This is, of course, not a great algorithm. But it sometimes works. It will hang if no solution is found (or if you're unlucky), and it can randomly take a very roundabout route to reach a solution. In fact, it is essentially identical to searching through all perturbations of seating arrangements, except it does so in a random order and can sometimes recheck duplicate arrangements. So yeah, not too great.
So we can make an improvement: Only keep a swap if it improves the seating arrangement:
def findGoodSeating2 (names):
table = names[:]
penalty = tablePenalty(enemies, table)
while penalty > 0:
newtable = table[:]
i, j = random.sample(range(0, len(table)), 2)
newtable[i], newtable[j] = newtable[j], newtable[i]
newpenalty = tablePenalty(enemies, newtable)
if newpenalty <= penalty: # Keep improvements.
table = newtable
penalty = newpenalty
return table
Here we use <= rather than <. This is actually important for our simple algorithm here. If we simply use < we can easily get stuck in situations where no swap improves the arrangement. By using <= we also keep swaps that don't hurt us, which provides a little extra "kick" to help nudge us out of ruts. This algorithm will work pretty well, and you might want to stop here. However, there is one more change you could consider making:
def findGoodSeating3 (names):
table = names[:]
penalty = tablePenalty(enemies, table)
stuck = 0
while penalty > 0:
newtable = table[:]
i, j = random.sample(range(0, len(table)), 2)
newtable[i], newtable[j] = newtable[j], newtable[i]
newpenalty = tablePenalty(enemies, newtable)
stuck = stuck + 1
if newpenalty < penalty:
table = newtable
penalty = newpenalty
stuck = 0
elif stuck > 50: # An arbitrary threshold.
random.shuffle(table)
penalty = tablePenalty(enemies, table)
stuck = 0
return table
This is almost the same as above except you'll notice we use < -- we strictly keep improvements. In this variant the "nudge" is provided by logic that, after 50 (you can tweak this number) swaps that don't improve the situation, we just randomly shuffle the table and start over in hopes of finding a solution from there.
Here is a full demo:
import random;
# A list of names to test with.
names = [ 'Clarke', 'Octavia', 'Bellamy', 'Jaha', 'Murphy', 'Finn',
'Abby', 'Alie', 'Lexa', 'Kane', 'Lincoln' ]
# Build list of people each person can't sit next to.
enemies = {}
for name in names:
choices = [ x for x in names if x != name ]
enemies[name] = random.sample(choices, 3) # 3 enemies per person
print "%s: %s" % (name, enemies[name])
#-------------------------------------------------------------------
def tablePenalty (enemies, table):
penalty = 0
for k, name in enumerate(table):
p = (k + len(table) - 1) % len(table)
n = (k + 1) % len(table)
if table[p] in enemies[name]:
penalty = penalty + 1
if table[n] in enemies[name]:
penalty = penalty + 1
return penalty
def findGoodSeating1 (names):
table = names[:]
while tablePenalty(enemies, table) > 0:
i, j = random.sample(range(0, len(table)), 2)
table[i], table[j] = table[j], table[i]
return table
def findGoodSeating2 (names):
table = names[:]
penalty = tablePenalty(enemies, table)
while penalty > 0:
newtable = table[:]
i, j = random.sample(range(0, len(table)), 2)
newtable[i], newtable[j] = newtable[j], newtable[i]
newpenalty = tablePenalty(enemies, newtable)
if newpenalty <= penalty:
table = newtable
penalty = newpenalty
return table
def findGoodSeating3 (names):
table = names[:]
penalty = tablePenalty(enemies, table)
stuck = 0
while penalty > 0:
newtable = table[:]
i, j = random.sample(range(0, len(table)), 2)
newtable[i], newtable[j] = newtable[j], newtable[i]
newpenalty = tablePenalty(enemies, newtable)
stuck = stuck + 1
if newpenalty < penalty:
table = newtable
penalty = newpenalty
stuck = 0
elif stuck > 3 * len(table):
random.shuffle(table)
penalty = tablePenalty(enemies, table)
stuck = 0
return table
# Test them:
print findGoodSeating1(names)
print findGoodSeating2(names)
print findGoodSeating3(names)
An example output:
Clarke: ['Bellamy', 'Lincoln', 'Octavia']
Octavia: ['Jaha', 'Abby', 'Bellamy']
Bellamy: ['Clarke', 'Abby', 'Alie']
Jaha: ['Finn', 'Lincoln', 'Alie']
Murphy: ['Octavia', 'Jaha', 'Lexa']
Finn: ['Lexa', 'Clarke', 'Alie']
Abby: ['Lexa', 'Clarke', 'Jaha']
Alie: ['Clarke', 'Kane', 'Lincoln']
Lexa: ['Murphy', 'Alie', 'Finn']
Kane: ['Lexa', 'Alie', 'Bellamy']
Lincoln: ['Murphy', 'Clarke', 'Octavia']
['Octavia', 'Lexa', 'Jaha', 'Bellamy', 'Murphy', 'Clarke', 'Kane', 'Finn', 'Lincoln', 'Abby', 'Alie']
['Clarke', 'Jaha', 'Bellamy', 'Lexa', 'Octavia', 'Alie', 'Abby', 'Finn', 'Lincoln', 'Kane', 'Murphy']
['Murphy', 'Clarke', 'Jaha', 'Lexa', 'Bellamy', 'Lincoln', 'Kane', 'Octavia', 'Finn', 'Abby', 'Alie']
Since the algorithms are random, we end up with 3 different, but satisfactory, solutions.
Now there's some important notes about the above algorithms:
- You can tweak the thresholds and stuff, you really just have to experiment.
- All will hang if there is no solution. All also run the risk of randomly taking a long time even if there is a solution, but the chances of this are low enough that for realistic data sets you may never notice.
- The way to stop it from hanging, which I did not implement only for brevity is easy: Just limit the algorithms to a maximum number of iterations. If you do:
- For the first variant your results will effectively be random.
- For the second variant your result will be the best so far.
- For the third variant you probably want to track the overall best, since you could hit your iteration limit after a random shuffle and lose info about an even better earlier initial state.
- These algorithms are not ideal -- they are simple. And for this application they perform well enough. This is the important part.
- You might want to experiment by only, say, swapping people who are seated next to enemies with random positions. This may or may not improve performance.
Anyways this wasn't intended to prove what the best algorithm is, only to give you some ideas on how to start with a fuzzier approach. Personally, one of these is the way I would go for this, because while you certainly could find a graph-based solution (or even a direct search -- essentially similar to constraint-based in this case -- place a person, place the person next to them, when you hit a bad arrangement back out and try the next perturbation), and while it could certainly be very fast if you do, this is just easy.
