有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
请你计算,一共有多少种不同的剪取方法。
用了奇怪的伪函数式编程把这道题做出来了,一开始深搜里嵌套了一个深搜,运算速度极其慢,最后用了官方库的排列组合才解决掉,有时间需要看一看官方库的全排列是怎么写的
def is_connect(path):
pathed=[]
def dfs(p,path):
nonlocal pathed
for d in [(0,1),(1,0),(-1,0),(0,-1)]:
npx=p[0]+d[0]
npy=p[1]+d[1]
if npx >=0 and npx<3 and npy>=0 and npy<4:
if (npx,npy) in path:
if (npx,npy) not in pathed:
pathed.append((npx,npy))
dfs((npx,npy),path)
for p in path:
dfs(p,path)
break
if len(pathed)==len(path):
return True
else:
return False
import copy
import itertools
stamp=[[0,1,2,3],
[4,5,6,7],
[8,9,10,11]]
last_path=[]
nums=0
#注意第一个for在外层
position=[(x,y)for x in range(3) for y in range(4)]
for perm in itertools.combinations(range(12),5):
#一维转二维
elem_p=[(e//4,e%4) for e in perm]
if is_connect(elem_p):
last_path.append(elem_p)
nums+=1
print(nums)