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

Postby Wolfkeeper » Sat May 07, 2016 5:24 pm UTC

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? :wink:

User avatar
Flumble
Yes Man
Posts: 2261
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Seating problem

Postby Flumble » Sat May 07, 2016 9:44 pm UTC

Does proof by example count? :P

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 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 [edit] 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.

[edit]
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

Postby Wolfkeeper » Sat May 07, 2016 9:52 pm UTC

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

Postby lorb » Sat May 07, 2016 10:40 pm UTC

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/

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

Re: Seating problem

Postby PM 2Ring » Sun May 08, 2016 11:54 am UTC

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_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.
= [(j, i) for i in range(1, 10) for j in range(i) if i-!= 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()

= {}
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...')
= 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)]

User avatar
Flumble
Yes Man
Posts: 2261
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Seating problem

Postby Flumble » Tue May 10, 2016 7:50 pm UTC

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. :oops: (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 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 mind-bogglingly 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 do-notation
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 k-course layouts from available (k-1)-course layouts
meal2 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 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 (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 where
import Prelude
import Data.List

meal 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)) + 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))

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

Re: Seating problem

Postby arbiteroftruth » Wed May 11, 2016 6:29 pm UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests