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

Question

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

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

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

- Piniu

---

这个问题更适合在math.stackexchange.com上讨论。 - Karl Knechtel

我尊敬地不同意@Karl Knechtel的观点。数学是编程和计算机科学的重要组成部分。 - Borealis

Answer 1

让counts成为一个数组，其中counts[k]表示第k个符号的数量。

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

来自《像sum()一样但是用于乘法的Python函数是什么？ 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))

在另一种语言中，我们需要担心由于计算大的阶乘或乘法计算多个小阶乘而出现的大数字。通常情况下，计算会超出最大整数或浮点数规范。但是在Python中，所有整数操作都是精确的，需要多少位就采取多少位，且设计上不会发生整数溢出。速度可能会成为一个问题，但那是另外一回事。

如何使用：

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

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

要执行此操作的数学方法，请参见维基百科：排列组合：多重集合的排列组合

- Paul

Answer 2

如果每个字母有N_i个副本，则您想要的数字是多项式系数

(N_1 + N_2 + ... + N_k)!/(N_1! N_2! ... N_k!)

有关在不溢出的情况下计算此内容的方法，请参见如何有效地计算多项式？.

- lhf