Table seating, what algorithm to use?

Question

So I have this problem and I need to figure out what kind of algorithm can solve it.

Given a group of people, and given who doesn't like whom within this group, arrange a seating for all people at a round table so that no one sits next to someone they do not like (if possible).

I just can't figure out how to approach it. Basically I drew it as a directed graph with nodes representing a person and edges going from people who doesn't like someone to the one they don't like. Then, you want to arrange the nodes in a circle so that no edge is between two nodes next to each other. I couldn't find an algorithm that solves this kind of problem however.

Answer 1

To make your statement a bit easier, assume that you "invert" your graph such that you have edges between two guests if and only if they can be seated next to each other.

Now, what you are looking for is a cycle (closed walk) that contains each vertex at exactly once. This is called a Hamiltonian cycle. It's NP-hard in general (so is your problem as any instance of Hamiltonian cycle can be reduced to your problem), but under certain conditions, it's easier.

Genetic algorithms (like JasonC mentioned) could solve the problem most times, Integer Linear programming would be an option, Constraint programming, too.

Answer 2

Honestly, I'd go with some sort of annealing-ish algorithm. Basically:

1. Start with a set of rules and an initial arrangement.
2. Make a random change, keeping it if it improves.
3. 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.