这是一个家庭作业问题，但我已经做了一段时间，我不明白我做错了什么。任何帮助都将不胜感激。
根据以下规则，计算N位晚餐客人围绕圆桌的安排方式：
最初，所有的客人都坐在一张没有空座位的圆桌上。为了鼓励交谈，主人让每位客人站起来，然后坐在三把椅子中的一把：原来的椅子，左边一把，右边一把。
所有客人都必须坐下。
晚餐客人有多少种不同的安排？
如果客人的座位号不同，两种安排是不同的。
ABCD与DABC不同。但是，没有人能移动超过两个地方，
即BCAD将无效，因为A已移动了两个位置。
部分解决方案是：
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
我的代码最多可以为5位客人工作，但对于6位客人，我得到19种不同的安排。对于7位客人，我得到28个安排。我猜我的逻辑有问题，但我想不出来。
这是我的代码：
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)
最佳答案
下面是重构后的代码版本，以便更好地理解：
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
我认为问题在于你没有管理好“边缘”，即位置0可能被客人1（没有变化）、客人2（右邻居）或客人N（最后一个，是左邻居）占据。桌子上最后一个位置也是这样。因此，以下操作将起作用（将
imports放在一边）：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
还要注意，我在N>2中不使用阶乘；我只计算正确的排列数。
更好的是，下面使用了排列函数的惰性特性：
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
最后，这里有一个递归的解决方案。与您（和其他人）的方法相反，我不会生成每个排列，然后消除错误的排列；我从头开始创建解决方案。另外，我使用基于0的编号，这在我看来更为自然：
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
然后
for i in range(3, 8):
combos = dinner(i)
print(i, "guests can sit in", len(combos), "ways", combos)
产量
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]]
我希望这能有帮助。
关于python - 晚餐客人安排，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26347879/