以更快的方式获得排列计数

本文介绍了以更快的方式获得排列计数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 使用此代码来获得排列的计数在大数上很慢，因为分区部分需要很长时间来计算像100这样的数字的所有分区，并且由于RAM中的所有分区，这是非常消耗RAM的。有什么解决方案可以更快地计算排列的数量吗？谢谢。

如果有get_permutations_count(10,10)表示使用10个不同符号的长度为10的所有排列，如果有get_permutations_count(10,1)表示使用一个不同符号的长度为10的所有排列，则这些排列将是000000000011111111112222222222333333333...9999999999。

from sympy.utilities.iterables import partitions from sympy import factorial def get_permutations_count(all_symbols_count, used_symbols_count): m = n = all_symbols_count r = n - used_symbols_count while True: result = 0 for partition in partitions(r): length = 0 if 2 * r > n: for k, v in partition.items(): length += (k + 1) * v if length > n: pass else: C = binomial(m, n - r) d = n - r for v in partition.values(): C *= binomial(d, v) d -= v # permutations P = 1 for k in partition.keys(): for v in range(partition[k]): P *= factorial(k + 1) P = factorial(n) // P result += C * P return result if __name__ == "__main__": print(get_permutations_count(300, 270)) # takes long time to calculate print(get_permutations_count(10, 9) # prints: 163296000 print(get_permutations_count(10, 10)) # prints: 3628800 推荐答案

按照this答案，您可以找到计算此类排列数量的高效算法的派生。

它是通过使用问题的一般化来计算长度不一定等于字母表大小的序列来实现的。

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