python - 如何在不构建临时列表的情况下计算唯一排列的数量？

Question

如何计算这个数字而不是枚举所有排列然后创建集合来切断所有重复？

len(set(itertools.permutations('aaabbb')))
20

len(set(itertools.permutations('aabb')))
6

Answer 1

令 counts 为一个数组，其中 counts[k] = 第 k 个符号的计数。

我们需要一种让 python 轻松计算一堆乘法的方法，一个 product() 函数....

来自 What's the Python function like sum() but for multiplication? product()? :

from functools import reduce # Valid in Python 2.6+, required in Python 3
import operator

def product(X):
    return reduce(operator.mul, X, 1)

现在我们可以将排列数定义为:

def unique_permutations(counts):
    return math.factorial(sum(counts))/product(map(math.factorial, counts))

现在在另一种语言中，人们不得不担心由于采用大阶乘或乘以许多较小阶乘的结果可能出现在这个除法中的大数字。通常，在某些时候计算会溢出 MAXINT 或 MAXFLOAT 规范。但是在python中，所有的整数运算都是精确的，需要多少位数就取多少，设计上不会出现整数溢出。速度可能会成为一个问题，但那是另一回事。

使用方法:

>>> unique_permutations([3,3])
20

>>> unique_permutations([2,2])
6

有关如何执行此操作的数学，请参阅 Wikipedia: Permutation: Permutations of Multisets