Dinner
This is a homework problem, but I've been working on it for a while now and I don't understand what I am doing wrong. Any help would be appreciated.
Count the number of ways that Dinner N guests can organize themselves around the round table according to the following rules:
Initially, all guests sit at a round table with no empty seats. To encourage conversation, the host asks each guest to stand up and then sit in one of three chairs: the original chair, one to the left, or one to the right.
All guests must be seated.
How many different arrangements are there for dinner guests?
The two schemes are different if the chair number for any guest differs from one position in another.
ABCD is different from DABC. However, no person can move more than two seats, IE BCAD will be invalid because A has moved two seats.
Partial solutions:
3 guests can sit in 6 different ways
4 guests can sit in 9 different ways
5 guests can sit in 13 different ways
6 guests can sit in 20 different ways
7 guests can sit in 31 different ways
My code works for up to 5 guests, but for 6 guests I get 19 different arrangements. For 7 guests I get 28 arrangements. I guess there is something with my logic, but I cannot figure it out.
Here's my code:
def dinner_party_arrangements(N):
import itertools
if N > 10:
return('This function is not built for N > 10.')
else:
import math
result=math.factorial(N)
baseL=[]
main=list(range(N))
L=list(range(N+1))
L.remove(0)
combos=(list(itertools.permutations(L)))
for stuff in combos:
baseL.append(stuff)
for guests in baseL:
resultL=list(guests)
#looks at single tuple
for num in main:
a=num
b=num+1
c=num+2
if resultL[num] == a or resultL[num] == b or resultL[num] == c:
pass
else:
result=(result-1)
break
if N<3:
return(result)
else:
return(result+N)
source to share
Here's a refactored version of your code for better understanding:
import itertools
import math
def dinner_party_arrangements(N):
assert N <= 10, 'This function is not built for N > 10.'
result = math.factorial(N)
if N < 3:
return result
for guests in itertools.permutations(range(1, N+1)):
for num in range(N):
if guests[num] not in (num, num+1, num+2):
result -= 1
break
return result+N
I think the problem is that you are not controlling the "edges", i.e. position 0 can be occupied by guest 1 (unchanged), guest 2 (right neighbor) or guest N (last, which is left neighbor). The same goes for the last position on the table. So the following will work (leaving import
aside):
def dinner_party_arrangements(N):
assert N <= 10, 'This function is not built for N > 10.'
if N < 3:
return math.factorial(N)
allguests = list(itertools.permutations(range(1,N+1)))
result = len(allguests)
for guests in allguests:
for num in range(N):
if guests[num] not in (N if num==0 else num, num+1, 1 if num==N-1 else num+2):
result -= 1
break
return result
Also note that I am not using factorial in N> 2; I'll just count the number of correct vertices.
Moreover, the following takes advantage of the lazy nature of the permutation function:
def dinner_party_arrangements(N):
assert N <= 10, 'This function is not built for N > 10.'
if N < 3:
return math.factorial(N)
result = 0
for guests in itertools.permutations(range(1,N+1)):
for num in range(N):
if guests[num] not in (N if num==0 else num, num+1, 1 if num==N-1 else num+2):
break
else:
result += 1
return result
Finally, here's a recursive solution for this. Unlike your (and other peoples') approach, I don't generate every permutation and then fix the wrong ones; I am building solutions from scratch. Also, I use 0-based numbering, which seems more natural to me:
def dinner(gst):
assert gst > 2 # alogorith doesn't work for < 3 people
res = [] # result, the list of all possible combinations
def sub(current, pers):
if pers == gst: # base case of recursion; no more person to sit
res.append(current) # found one combo, add it to result
return # and stop here
for offset in (-1, 0, +1): # for each move (left, stay, right)
newpos = (pers + offset) % gst # compute new position
if current[newpos] is None: # seat is not yet taken
newcurrent = current[:] # create a copy of current (incomplete) combination
newcurrent[newpos] = pers # sit person pos at position newpos
sub(newcurrent, pers + 1) # and recurse for the other persons
sub([None]*gst, 0) # initialize a combi
return res
then
for i in range(3, 8):
combos = dinner(i)
print(i, "guests can sit in", len(combos), "ways", combos)
gives
3 guests can sit in 6 ways [[1, 2, 0], [2, 1, 0], [0, 1, 2], [0, 2, 1], [1, 0, 2], [2, 0, 1]]
4 guests can sit in 9 ways [[1, 2, 3, 0], [3, 1, 2, 0], [3, 2, 1, 0], [0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [1, 0, 2, 3], [1, 0, 3, 2], [3, 0, 1, 2]]
5 guests can sit in 13 ways [[1, 2, 3, 4, 0], [4, 1, 2, 3, 0], [4, 1, 3, 2, 0], [4, 2, 1, 3, 0], [0, 1, 2, 3, 4], [0, 1, 2, 4, 3], [0, 1, 3, 2, 4], [0, 2, 1, 3, 4], [0, 2, 1, 4, 3], [1, 0, 2, 3, 4], [1, 0, 2, 4, 3], [1, 0, 3, 2, 4], [4, 0, 1, 2, 3]]
6 guests can sit in 20 ways [[1, 2, 3, 4, 5, 0], [5, 1, 2, 3, 4, 0], [5, 1, 2, 4, 3, 0], [5, 1, 3, 2, 4, 0], [5, 2, 1, 3, 4, 0], [5, 2, 1, 4, 3, 0], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 5, 4], [0, 1, 2, 4, 3, 5], [0, 1, 3, 2, 4, 5], [0, 1, 3, 2, 5, 4], [0, 2, 1, 3, 4, 5], [0, 2, 1, 3, 5, 4], [0, 2, 1, 4, 3, 5], [1, 0, 2, 3, 4, 5], [1, 0, 2, 3, 5, 4], [1, 0, 2, 4, 3, 5], [1, 0, 3, 2, 4, 5], [1, 0, 3, 2, 5, 4], [5, 0, 1, 2, 3, 4]]
7 guests can sit in 31 ways [[1, 2, 3, 4, 5, 6, 0], [6, 1, 2, 3, 4, 5, 0], [6, 1, 2, 3, 5, 4, 0], [6, 1, 2, 4, 3, 5, 0], [6, 1, 3, 2, 4, 5, 0], [6, 1, 3, 2, 5, 4, 0], [6, 2, 1, 3, 4, 5, 0], [6, 2, 1, 3, 5, 4, 0], [6, 2, 1, 4, 3, 5, 0], [0, 1, 2, 3, 4, 5, 6], [0, 1, 2, 3, 4, 6, 5], [0, 1, 2, 3, 5, 4, 6], [0, 1, 2, 4, 3, 5, 6], [0, 1, 2, 4, 3, 6, 5], [0, 1, 3, 2, 4, 5, 6], [0, 1, 3, 2, 4, 6, 5], [0, 1, 3, 2, 5, 4, 6], [0, 2, 1, 3, 4, 5, 6], [0, 2, 1, 3, 4, 6, 5], [0, 2, 1, 3, 5, 4, 6], [0, 2, 1, 4, 3, 5, 6], [0, 2, 1, 4, 3, 6, 5], [1, 0, 2, 3, 4, 5, 6], [1, 0, 2, 3, 4, 6, 5], [1, 0, 2, 3, 5, 4, 6], [1, 0, 2, 4, 3, 5, 6], [1, 0, 2, 4, 3, 6, 5], [1, 0, 3, 2, 4, 5, 6], [1, 0, 3, 2, 4, 6, 5], [1, 0, 3, 2, 5, 4, 6], [6, 0, 1, 2, 3, 4, 5]]
Hope this helps.
source to share
Here's my approach. It is very slow for large n, but it works.
from itertools import permutations
def arrange( n ):
# First, place all your guests (0 - n) into an array
positions = range( n )
arrangements = 0
# Iterate over every possible arrangement of guests
for arrangement in permutations( positions ):
# begin by assuming the iteration is "valid", that is, no guest
# hopped more than one spot
is_valid = True
# Now iterate over all your guests
for i in range( n ):
# If the guest moved more than one spot, this permutation is
# invalid and we can throw it out
pos_dif = abs( arrangement.index( i ) - positions.index( i ) )
if pos_dif > 1 and pos_dif != n-1:
is_valid = False
break
# Otherwise, the iteration is valid and we can increment our count
if is_valid:
arrangements += 1
return arrangements
source to share
My approach was similar to the post above:
def mydin(n):
import itertools
initial_table = range(n)
poss_tables = set(itertools.permutations(initial_table))
validTables = []
for table in poss_tables:
if isValid(initial_table,table):
validTables.append(table)
print len(validTables)
return len(validTables)
def isValid(initial_table,arrangement):
size = initial_table[-1]
for i in range(len(initial_table)):
if i == size:
if arrangement[i] in (initial_table[i-1],initial_table[i],initial_table[0]):
continue
else:
return False
elif arrangement[i] in [initial_table[i-1],initial_table[i],initial_table[i+1]]:
continue
else:
return False
return True
for n in range(3,11):
mydin(n)
and for my output I got
6 9 13 20 31 49 78 125
source to share