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?
Seating problem
Moderators: gmalivuk, Moderators General, Prelates
Re: Seating problem
Does proof by example count?
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 bruteforceable. (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 [edit] since running the above code for 9 people resulted in only 3 courses, I tried bruteforcing it with
...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.
[edit]
For completeness' sake, here's the list of longest meals for up to 12 people, found using the almostbutnotcompletely exhaustive algorithm:
As you can see, the 3 courses for 9 people looks really out of place.
Code: Select all
module Main where
import Prelude
import 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 bruteforceable. (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)
*
Code: Select all
courses2 c n = find disjoint (map ((:) [1..n]) $ sequence $ replicate (c1) $ 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 (c1) $ 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.
[edit]
For completeness' sake, here's the list of longest meals for up to 12 people, found using the almostbutnotcompletely 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.

 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.
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/
http://decodedarfur.org/
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.
Here are the first 10 solutions it finds:
Here are a few more:
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_function
import sys
from itertools import permutations, product
#Algorithm X functions
def 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 cols
def 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 collection
def 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 ij != 5]
#Convert X to an actual set to make it easier to verify solutions
cols = 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 collection
print('Inverting subset collection...')
X = exact_cover(X, Y)
#Use the ordered permutation as the first permutation
initial = 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)]
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 ncourse 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 courses
checkEatingRAM = [[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 mindbogglingly slow.
[pseudoedit]
4th time's a charm:
Code: Select all
module Main where
import Prelude
import Data.List(permutations,intersect,null) actually useful stuff
import Control.Monad(guard) this one's only for the specific case
import Data.Maybe(maybeToList) these imports are only for the main function
import Text.Read(readMaybe)
import System.Environment(getArgs)
main function so it's usable if you want it compiled
main = 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 donotation
meal = 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 kcourse layouts from available (k1)course layouts
meal2 n c = meal' c
where
meal' 0 = [[]]
meal' k = [l:ls  ls < meal' (k1), l < layouts, (concatMap pairs ls) `disjoint` (pairs l)]
layouts = map (1:) $ permutations [2..n]
still can't live without these functions
pairs 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 (n1)/2 disjoint layouts simply by putting people in the order [1,1+m,n1+m,2+m,n2+m,...,(n1)/2+m] for m=[1..(n1)/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 (n1)/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 where
import Prelude
import Data.List
meal n
 odd n = [ 1 : (map adjustValue $ interleave [k+m  k < range] [nk+m  k < range])  m < range]
 otherwise = map (insertAt n (n `div` 2)) (meal (n1))
where
range = [1..(n1) `div` 2]
adjustValue x = (x `mod` (n1)) + 2
insertAt x k list = before ++ [x] ++ after
where (before,after) = splitAt k list
interleave (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 pairing
allDisjoint 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))

 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 nonisomorphic, noncompound 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 counterclockwise, 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, ... (n1)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.
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 counterclockwise, 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, ... (n1)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.
Who is online
Users browsing this forum: No registered users and 6 guests