以更快的方式计算排列

Question

使用此代码来计算排列对于大数字来说很慢，因为分区部分需要很长时间来计算像 100 这样的数字的所有分区，并且由于 ram 中的所有分区，它非常消耗 ram .以更快的方式计算排列的任何解决方案？谢谢。

如果我们有 get_permutations_count(10,10) 意味着使用 10 个不同符号的长度为 10 的所有排列如果我们有 get_permutations_count(10,1) 意味着使用 1 个不同符号的长度为 10 的所有排列为 10，因为这些排列将是 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

Answer 1

根据回答，您可以找到计算此类排列数的有效算法的推导。

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

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

以更快的方式计算排列

Getting count of permutations in a faster way

python

permutation