import itertools
import re
import string
import time


def is_valid(arrangement):
    table = arrangement.lower()
    return table[0] != table[-1] and not re.search(r'(\w)\1', table)


def permutations(people, preset):
    if preset is None:
        preset = people[0] + '_' * (len(people) - 1)
    unused = [person for person in people if person not in preset]
    cases = itertools.permutations(unused)
    template = preset.replace('_', '{}')
    return (template.format(*p) for p in cases)


def get_valid_seatings(people, preset=None):
    if preset is None:
        preset = people[0] + '_' * (len(people) - 1)
    cases = permutations(people, preset)
    return [c for c in cases if is_valid(c)]


def count_seatings(num_couples):
    people = string.ascii_lowercase[:num_couples] + string.ascii_uppercase[:num_couples]
    return len(get_valid_seatings(people))


for i in range(1, 6):
    start = time.time()
    seatings = count_seatings(i)
    end = time.time()
    print('{} couples: {} -- {:0.3f}s'.format(i, seatings, end - start))
# Try one with pre-seatings
couples = 'abcdeABCDE'
impatient = 'a__bc__A__'
start = time.time()
seatings = len(get_valid_seatings(couples, impatient))
end = time.time()
print('4 impatient people: {} -- {:0.3f}s'.format(seatings, end - start))