## Seating problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Wolfkeeper
Posts: 132
Joined: Fri Sep 12, 2008 1:59 am UTC

### Seating problem

This is a real world problem, I think I have an answer, but I'm not sure the proof is entirely solid, and I thought it was vaguely amusing.

We need to seat ten people at a table for a meal, for 4 courses, the people are to be reseated at each course, but this must be done so that no two people sit next to each other on either side, for more than one course. The table is topologically a circle and has ten places.

Is this possible to do?

You'd think it would be easy, because each person sits next to only 8 people over the course of the meal, so how hard could it be?

Flumble
Yes Man
Posts: 2266
Joined: Sun Aug 05, 2012 9:35 pm UTC

### Re: Seating problem

Does proof by example count?

Code: Select all

`module Main whereimport Preludeimport Data.List(permutations,intersect,null,find)layout excludedPairs = find (null . intersect excludedPairs . pairs) (permutations [1..10])pairs xs = zipWith orderedPair xs (shift xs)   where      shift (x:xs) = xs ++ [x]      orderedPair a b = if a<b then (a,b) else (b,a)courses = courses' []   where courses' excludedPairs      | Just someLayout <- layout excludedPairs = (someLayout : courses' (excludedPairs ++ pairs someLayout))      | otherwise = []`

take 4 courses results in [[1,2,3,4,5,6,7,8,9,10],[3,5,2,4,6,9,7,1,8,10],[6,8,5,7,4,1,3,9,2,10],[5,1,9,4,8,3,6,2,7,10]]. These are definitely 4 consecutive courses without duplicate pairings.
It's nice when a problem is just at the edge of being brute-forceable. (though if layout choices in earlier courses do effect the availability of later layouts, I'm simply in luck* and the actual complexity would be Θ(n!^(n/2)) instead of Θ(n!*(n/2)), i.e. roughly 10^20 times as slow)

*footnote pending  since running the above code for 9 people resulted in only 3 courses, I tried brute-forcing it with

Code: Select all

`courses2 c n = find disjoint (map ((:) [1..n]) \$ sequence \$ replicate (c-1) \$ permutations [1..n])   where disjoint = and . snd . mapAccumL (\union xs -> (union ++ (pairs xs), null \$ intersect union (pairs xs))) []courses3 c n = find disjoint \$ map ([1..n]:) \$ sequence \$ replicate (c-1) \$ permutations [1..n]   where      disjoint = isJust . foldl f (Just []) . concatMap pairs      f Nothing _ = Nothing      f (Just xs) x = if (x `elem` xs) then Nothing else Just (x:xs)`

...but those only brought my computer to a crawl thanks to GHC's memory management. So a proof for the number of courses for arbitrary n≥2 would be nice.

For completeness' sake, here's the list of longest meals for up to 12 people, found using the almost-but-not-completely exhaustive algorithm:

Code: Select all

`" 2 people", "1 course ", "[[1,2]]"" 3 people", "1 course ", "[[1,2,3]]"" 4 people", "1 course ", "[[1,2,3,4]]"" 5 people", "2 courses", "[[1,2,3,4,5],[2,4,1,3,5]]"" 6 people", "2 courses", "[[1,2,3,4,5,6],[2,5,3,1,4,6]]"" 7 people", "3 courses", "[[1,2,3,4,5,6,7],[3,6,2,4,1,5,7],[4,6,1,3,5,2,7]]"" 8 people", "3 courses", "[[1,2,3,4,5,6,7,8],[3,7,4,2,5,1,6,8],[4,1,7,5,3,6,2,8]]"" 9 people", "3 courses", "[[1,2,3,4,5,6,7,8,9],[4,8,3,5,2,6,1,7,9],[5,8,6,4,1,3,7,2,9]]""10 people", "4 courses", "[[1,2,3,4,5,6,7,8,9,10],[3,5,2,4,6,9,7,1,8,10],[6,8,5,7,4,1,3,9,2,10],[5,1,9,4,8,3,6,2,7,10]]""11 people", "5 courses", "[[1,2,3,4,5,6,7,8,9,10,11],[4,6,3,5,2,7,10,8,1,9,11],[6,9,7,5,8,4,1,3,10,2,11],[7,1,5,10,6,2,4,9,3,8,11],[5,9,2,8,6,1,10,4,7,3,11]]""12 people", "5 courses", "[[1,2,3,4,5,6,7,8,9,10,11,12],[4,7,5,3,6,2,8,11,9,1,10,12],[7,9,6,8,5,10,4,1,3,11,2,12],[5,1,6,4,11,7,3,8,10,2,9,12],[8,1,7,10,6,11,5,2,4,9,3,12]]"`

As you can see, the 3 courses for 9 people looks really out of place.
Last edited by Flumble on Sat May 07, 2016 11:23 pm UTC, edited 3 times in total.

Wolfkeeper
Posts: 132
Joined: Fri Sep 12, 2008 1:59 am UTC

### Re: Seating problem

Woah. Very nice, I'm impressed. I didn't think it was possible; but I couldn't definitely prove it, but it looked suspiciously impossible. I feel a little better though that the answer looks so scrambled.

lorb
Posts: 405
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

### Re: Seating problem

You can improve by assuming that one slot is fixed (one person never gets up). The table being in effect a circle loses one degree of freedom so you only have to search in the permutations of the nine other people.
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: Seating problem

Here's a Python 2 / Python 3 program that finds solutions. I haven't looked at Flumble's code, but I am using lorb's optimization. My approach is to express the problem as an Exact Cover problem.

Our goal is to find sets of 4 permutations so that each of the 10 people get exactly 8 neighbours over the whole meal. Each person has 9 possible neighbours, so we need to eliminate one of them. A simple symmetrical way to do that is to ensure that persons who are initially opposite one another are never neighbours. If we give each person an index number `i` from 0 to 9, the person initially opposite has index `i + 5 mod 10`. We treat person zero as fixed to reduce the number of permutations to examine, this also makes it easier to treat the list of people as circular.

On my old 2GHz machine this program takes about 20 seconds to construct the list of all legal permutations, i.e., permutations with person `i` and `i + 5 mod 10` are eliminated. A few seconds later it starts churning out solutions.

This program contains some code to verify that the found solutions are correct, but I've commented that out to improve the speed slightly.

Code: Select all

`#!/usr/bin/env python""" A seating problem submitted by Wolfkeeper on xkcd Mathematics.    We need to seat ten people at a table for a meal, for 4 courses, the    people are to be reseated at each course, but this must be done so that    no two people sit next to each other on either side, for more than one    course. The table is topologically a circle and has ten places.    See http://forums.xkcd.com/viewtopic.php?f=17&t=115463    -----------------------------------------------    This program finds solutions using Knuth's Algorithm X for the     Exact Cover problem. The standard implementation of this algorithm,    "Dancing Links", uses doubly linked circular lists.    This Python implementation using dicts instead was written by Ali Assaf.    See http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html    and http://www.cs.mcgill.ca/~aassaf9/python/sudoku.txt    -----------------------------------------------    Our goal is to find sets of 4 permutations so that each of the 10 people    get exactly 8 neighbours over the whole meal. Each person has 9 possible    neighbours, so we need to eliminate one of them. A simple symmetrical    way to do that is to ensure that persons who are initially opposite one    another are never neighbours. If we give each person an index number `i`    from 0 to 9, the person initially opposite has index `i + 5 mod 10`. We    treat person zero as fixed to reduce the number of permutations to    examine, this also makes it easier to treat the list of people as    circular.    Written by PM 2Ring 2016.05.08"""from __future__ import print_functionimport sysfrom itertools import permutations, product#Algorithm X functionsdef solve(X, Y, solution=[]):    if not X:        yield list(solution)    else:        c = min(X, key=lambda c: len(X[c]))        for r in list(X[c]):            solution.append(r)            cols = select(X, Y, r)            for s in solve(X, Y, solution):                yield s            deselect(X, Y, r, cols)            solution.pop()def select(X, Y, r):    cols = []    for j in Y[r]:        for i in X[j]:            for k in Y[i]:                if k != j:                    X[k].remove(i)        cols.append(X.pop(j))    return colsdef deselect(X, Y, r, cols):    for j in reversed(Y[r]):        X[j] = cols.pop()        for i in X[j]:            for k in Y[i]:                if k != j:                    X[k].add(i)#Invert subset collectiondef exact_cover(X, Y):    newX = dict((j, set()) for j in X)    for i, row in Y.items():        for j in row:            newX[j].add(i)    return newX#----------------------------------------------------------------------#Person i must be seated next to all others except person abs(i - 5)bad = set((i, i + 5) for i in range(5))#Set to cover.X = [(j, i) for i in range(1, 10) for j in range(i) if i-j != 5]#Convert X to an actual set to make it easier to verify solutionscols = set(X)#Subsets to cover X with.print('Building all legal permutations', end='')sys.stdout.flush()Y = {}for i, seq in enumerate(permutations(range(1, 10))):    # Find all pairs of neighbours in seq. 0 is also included in    # seq at the beginning and end to make the sequence circular    neighbours = [min(t, t[::-1]) for t in zip((0,) + seq, seq + (0,))]    #Eliminate permutations with bad neighbours    if not bad.intersection(neighbours):        Y[seq] = neighbours    if i % 10000 == 0:        print('.', end='')        sys.stdout.flush()print('\nNumber of permutations:', len(Y))#Invert subset collectionprint('Inverting subset collection...')X = exact_cover(X, Y)#Use the ordered permutation as the first permutationinitial = tuple(range(1, 10))initial_neighbours = Y[initial]select(X, Y, initial)print('Searching...')for count, s in enumerate(solve(X, Y, []), 1):    ## Check that solution is valid.     #all_neighbours = set(initial_neighbours)    #for seq in s:        #all_neighbours.update(Y[seq])    #assert all_neighbours == cols, (s, all_neighbours)    print(count, s) `

Here are the first 10 solutions it finds:

Code: Select all

`1 [(7, 9, 5, 2, 4, 6, 3, 1, 8), (2, 9, 3, 5, 1, 7, 4, 8, 6), (3, 7, 5, 8, 2, 6, 9, 1, 4)]2 [(7, 9, 5, 2, 4, 6, 3, 1, 8), (2, 9, 3, 5, 1, 7, 4, 8, 6), (4, 1, 9, 6, 2, 8, 5, 7, 3)]3 [(7, 9, 5, 2, 4, 6, 3, 1, 8), (3, 7, 4, 8, 5, 1, 9, 2, 6), (2, 8, 6, 9, 3, 5, 7, 1, 4)]4 [(7, 9, 5, 2, 4, 6, 3, 1, 8), (3, 7, 4, 8, 5, 1, 9, 2, 6), (4, 1, 7, 5, 3, 9, 6, 8, 2)]5 [(7, 9, 5, 2, 4, 6, 3, 1, 8), (6, 9, 1, 5, 3, 7, 4, 8, 2), (4, 1, 7, 5, 8, 6, 2, 9, 3)]6 [(7, 9, 5, 2, 4, 6, 3, 1, 8), (6, 9, 1, 5, 3, 7, 4, 8, 2), (3, 9, 2, 6, 8, 5, 7, 1, 4)]7 [(7, 9, 5, 2, 4, 6, 3, 1, 8), (2, 9, 1, 5, 3, 7, 4, 8, 6), (3, 9, 6, 2, 8, 5, 7, 1, 4)]8 [(7, 9, 5, 2, 4, 6, 3, 1, 8), (2, 9, 1, 5, 3, 7, 4, 8, 6), (4, 1, 7, 5, 8, 2, 6, 9, 3)]9 [(7, 9, 5, 2, 4, 6, 3, 1, 8), (6, 2, 9, 1, 4, 8, 5, 7, 3), (4, 7, 1, 5, 3, 9, 6, 8, 2)]10 [(7, 9, 5, 2, 4, 6, 3, 1, 8), (6, 2, 9, 1, 4, 8, 5, 7, 3), (2, 8, 6, 9, 3, 5, 1, 7, 4)]`

Here are a few more:

Code: Select all

`100 [(8, 6, 9, 5, 2, 4, 1, 3, 7), (2, 6, 3, 5, 7, 9, 1, 8, 4), (6, 4, 7, 1, 5, 8, 2, 9, 3)]200 [(2, 4, 8, 6, 3, 5, 9, 1, 7), (6, 9, 2, 8, 5, 1, 4, 7, 3), (4, 6, 2, 5, 7, 9, 3, 1, 8)]300 [(3, 1, 7, 9, 5, 8, 2, 6, 4), (6, 8, 1, 4, 7, 5, 3, 9, 2), (8, 4, 2, 5, 1, 9, 6, 3, 7)]400 [(4, 1, 3, 7, 5, 9, 6, 2, 8), (3, 6, 4, 2, 5, 8, 1, 9, 7), (6, 8, 4, 7, 1, 5, 3, 9, 2)]500 [(3, 6, 8, 4, 2, 9, 5, 1, 7), (6, 4, 1, 9, 7, 3, 5, 8, 2), (4, 7, 5, 2, 6, 9, 3, 1, 8)]600 [(2, 6, 4, 7, 3, 5, 9, 1, 8), (4, 1, 7, 5, 8, 2, 9, 3, 6), (7, 9, 6, 8, 4, 2, 5, 1, 3)]700 [(2, 8, 1, 7, 3, 5, 9, 6, 4), (3, 9, 2, 6, 8, 4, 1, 5, 7), (6, 3, 1, 9, 7, 4, 2, 5, 8)]800 [(7, 9, 5, 3, 6, 4, 1, 8, 2), (6, 2, 5, 1, 9, 3, 7, 4, 8), (4, 2, 9, 6, 8, 5, 7, 1, 3)]900 [(8, 1, 5, 9, 2, 6, 3, 7, 4), (2, 5, 7, 9, 3, 1, 4, 8, 6), (7, 1, 9, 6, 4, 2, 8, 5, 3)]`

Flumble
Yes Man
Posts: 2266
Joined: Sun Aug 05, 2012 9:35 pm UTC

### Re: Seating problem

PM 2Ring wrote:Here's a Python 2 / Python 3 program that finds solutions. I haven't looked at Flumble's code, but I am using lorb's optimization. My approach is to express the problem as an Exact Cover problem.

That's kind of what I'm doing too, by generating 4 layouts at a time and checking whether the pairings are disjoint (in the first attempt by taking the intersection of a current course layout and previous pairings, and in the second and third by concatenating all pairings and checking for duplicates). Though I'm relying on GHC to memoize partial results, like the disjointness of previous layouts (which is programmed in the first approach, but not the others) and the set of pairs belonging to a permutation. And it's very probably not caching those results. (it's also not written in a way that tells the compiler "yeah I'll be needing the pair vectors for all permutations" like your Python code does)

Unfortunately, it appears GHC is hogging resources while generating the n-course permutations. I.e. even checking whether one of your solutions (for 9 people with 4 courses) is among the search space either eats all my RAM (so at least it's caching something) or takes ages to complete:

Code: Select all

`--verify that [[1,2,3,4,5,6,7,8,9],[1,7,3,6,9,4,2,8,5],[1,4,8,6,2,7,9,5,3],[1,8,3,9,2,5,7,4,6]] is in the domain of course2's or course3's search space--since the first course is [0..8] and every course has (0:_) in the Python solution, only generate permutations for the other coursescheckEatingRAM = [[6, 2, 5, 8, 3, 1, 7, 4], [3, 7, 5, 1, 6, 8, 4, 2], [7, 2, 8, 1, 4, 6, 3, 5]] `elem` (sequence \$ replicate 3 \$ permutations [1..8])checkTakingToLong = [[6, 2, 5, 8, 3, 1, 7, 4], [3, 7, 5, 1, 6, 8, 4, 2], [7, 2, 8, 1, 4, 6, 3, 5]] `elem` [[l1,l2,l3] | l1 <- permutations [1..8], l2 <- permutations [1..8], l3 <- permutations [1..8]]`

Python 1 - Haskell 0: it's too easy to write something in Haskell that's mind-bogglingly slow.

[pseudoedit]
4th time's a charm:

Code: Select all

`module Main whereimport Preludeimport Data.List(permutations,intersect,null) --actually useful stuffimport Control.Monad(guard)                   --this one's only for the specific caseimport Data.Maybe(maybeToList)                --these imports are only for the main functionimport Text.Read(readMaybe)import System.Environment(getArgs)--main function so it's usable if you want it compiledmain = getArgs >>= (putStrLn . parse . concatMap (maybeToList.readMaybe))  where    parse []        = show meal    parse [n, c]    = show (meal2 n c)    parse [n, c, k] = show \$ take k (meal2 n c)    parse _         = "either supply no arguments or the number of participants and courses"--specific M(10,4) case with do-notationmeal = do    l1 <- [head layouts] --all permutations are isomorphic to relabelling people    l2 <- layouts    guard (pairs l1 `disjoint` pairs l2)    l3 <- layouts    guard ((pairs l1++pairs l2) `disjoint` pairs l3)    l4 <- layouts    guard ((pairs l1++pairs l2++pairs l3) `disjoint` pairs l4)    return [l1,l2,l3,l4]  where layouts = map (1:) \$ permutations [2..10] --all rotations of a layout are isomorphic--general case, generating k-course layouts from available (k-1)-course layoutsmeal2 n c = meal' c  where    meal' 0 = [[]]    meal' k = [l:ls | ls <- meal' (k-1), l <- layouts, (concatMap pairs ls) `disjoint` (pairs l)]    layouts = map (1:) \$ permutations [2..n]--still can't live without these functionspairs xs = zipWith orderedPair xs (shift xs)  where    shift (x:xs) = xs ++ [x]    orderedPair a b = (min a b, max a b)disjoint = ((.).(.)) null intersect --it's the booperator; it glues two functions (c->d) and (a->b->c); sorry, I just like pointfree code`

Well, one point for Haskell because this approach does work. Now it's hogging just as much RAM and processor time as the Python code (within an order of magnitude both ways).

[pseudoedit the second]
Well would you take a look at that. For odd n you can generate (n-1)/2 disjoint layouts simply by putting people in the order [1,1+m,n-1+m,2+m,n-2+m,...,(n-1)/2+m] for m=[1..(n-1)/2].
And it follows that with an even n you can insert the last person somewhere in every course. Since there's a difference of (n-1)/2 between the elements right in the middle of an odd layout, you can insert your even person there. So my final submission is simply:

Code: Select all

`module Main whereimport Preludeimport Data.Listmeal n  | odd n     = [ 1 : (map adjustValue \$ interleave [k+m | k <- range] [n-k+m | k <- range]) | m <- range]  | otherwise = map (insertAt n (n `div` 2)) (meal (n-1))  where    range = [1..(n-1) `div` 2]    adjustValue x = (x `mod` (n-1)) + 2insertAt x k list = before ++ [x] ++ after  where (before,after) = splitAt k listinterleave (x:xs) (y:ys) = (x:y:interleave xs ys)interleave xs     ys     = xs++ys--for verification; tests disjointness by checking whether there are duplicates of any pairingallDisjoint layouts = unique (concatMap pairs layouts)  where    unique xs = length xs == length (nub xs)    pairs  xs = zipWith (\x y -> (min x y, max x y)) xs (tail (cycle xs))`

arbiteroftruth
Posts: 481
Joined: Wed Sep 21, 2011 3:44 am UTC

### Re: Seating problem

Asking how many courses can be seated with n people is equivalent to asking how many non-isomorphic, non-compound stars can be made with n vertices.

For n=1, there's only one 'star' of a single vertex. For n=2, there's only the 'star' that is the line segment connecting the two vertices. For n=3, there are in one sense two 'stars': one that traverses the vertices clockwise and the other counter-clockwise, but these are isomorphic to each other, so there's only one solution.

For n=4, you have a square and a pair of crossing line segments. But the latter is a compound star, consisting of two separate line segments, so it doesn't count as a solution.

For any given n, you can produce different stars by picking a starting vertex and progressing around the vertices m at a time, for m from 1 to floor(n/2). Above that you'll get the same stars traversed in the opposite direction. But if m and n share any factors, you'll get a compound star, giving you fewer than floor(n/2) solutions. That's why n=9 only gets three courses, because one of the stars you'd need to get to four courses is actually three separate triangles.

So the maximum number of courses for n people is floor(φ(n)/2), where φ(n) is Euler's totient function.

Solutions can be generated as [0,k mod n, 2k mod n, 3k mod n, ... (n-1)k mod n] for all k coprime to n from 1 to floor(n/2).

Edit: Actually, I guess that's just a weak lower bound. The real answer will increase by using seating arrangements that correspond to irregular cycles on the vertices.