Tuesday, 1 February 2022

Getting count of permutations in a faster way

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 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


from Getting count of permutations in a faster way

No comments:

Post a Comment