Using this code to get count of permutations is slow on big numbers as the partition part takes long time to calculate all the partitions for a number like 100 and because of all the partitions in the ram, it is very ram consuming. Any solution to get count of permutations in a faster way? Thanks.

If we have get_permutations_count(10,10) means all the permutations in the length of 10 using 10 distinct symbols and If we have get_permutations_count(10,1) means all the permutations in the length of 10 using 1 distinct symbol which going to be 10 as those permutations will be 0000000000 1111111111 2222222222 333333333 ... 9999999999.

from sympy.utilities.iterables import partitions
from sympy import factorialdef get_permutations_count(all_symbols_count, used_symbols_count):m = n = all_symbols_countr = n - used_symbols_countwhile True:result = 0for partition in partitions(r):length = 0if 2 * r > n:for k, v in partition.items():length += (k + 1) * vif length > n:passelse:C = binomial(m, n - r)d = n - rfor v in partition.values():C *= binomial(d, v)d -= v# permutationsP = 1for k in partition.keys():for v in range(partition[k]):P *= factorial(k + 1)P = factorial(n) // Presult += C * Preturn resultif __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

Following this answer, you can find the derivation of efficient algorithms for counting the number of such permutation.

It is achieved by using a generalization of the problem to count sequences of a length not necessarily equals to the size of the alphabet.

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 0if length == 0:return 1 if distinct == 0 else 0else: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)

Then

get_permutations_count(n_symbols=300, length=300, distinct=270)

runs in ~0.5 second giving the answer

2729511887951350984580070745513114266766906881300774347439917775
7093985721949669285469996223829969654724957176705978029888262889
8157939885553971500652353177628564896814078569667364402373549268
5524290993833663948683375995196081654415976659499171897405039547
1546236260377859451955180752885715923847446106509971875543496023
2494854876774756172488117802642800540206851318332940739395445903
6305051887120804168979339693187702655904071331731936748927759927
3688881301614948043182289382736687065840703041231428800720854767
0713406956719647313048146023960093662879015837313428567467555885
3564982943420444850950866922223974844727296000000000000000000000
000000000000000000000000000000000000000000000000