代码在不增加不同符号、n-符号和长度的情况下可以正常工作。例如,在我的计算机上,当 n_symbols=512,length=512,distinct=300 时,会出现以下错误: RecursionError: maximum recursion depth exceeded in comparison,如果我增加 lru_cache 值,则会出现溢出错误。
我希望有一个非递归版本的代码。
我希望有一个非递归版本的代码。
from functools import lru_cache
@lru_cache
def get_permutations_count(n_symbols, length, distinct, used=0):
'''
- n_symbols: number of symbols in the alphabet
- length: the number of symbols in each sequence
- distinct: the number of distinct symbols in each sequence
'''
if distinct < 0:
return 0
if length == 0:
return 1 if distinct == 0 else 0
else:
return \
get_permutations_count(n_symbols, length-1, distinct-0, used+0) * used + \
get_permutations_count(n_symbols, length-1, distinct-1, used+1) * (n_symbols - used)
那么
get_permutations_count(n_symbols=300, length=300, distinct=270)
程序运行约0.5秒即可得出答案。
2729511887951350984580070745513114266766906881300774347439917775
7093985721949669285469996223829969654724957176705978029888262889
8157939885553971500652353177628564896814078569667364402373549268
5524290993833663948683375995196081654415976659499171897405039547
1546236260377859451955180752885715923847446106509971875543496023
2494854876774756172488117802642800540206851318332940739395445903
6305051887120804168979339693187702655904071331731936748927759927
3688881301614948043182289382736687065840703041231428800720854767
0713406956719647313048146023960093662879015837313428567467555885
3564982943420444850950866922223974844727296000000000000000000000
000000000000000000000000000000000000000000000000
math.factorial
和math.comb
或math.perm
?这样会非常快。否则,将递归函数转换为迭代函数需要在列表上推送和弹出值,而不是在堆栈上。 - Jerry101