python - 查找列表的唯一组合的最快方法

Question

我正在尝试解决从 Python 中的列表中获取唯一组合的一般问题

数学上来自 https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html我可以看到组合数的公式是 n!/r!(n-r)! 其中 n 是序列的长度，r 是要选择的数字。

如以下 python 所示，其中 n 为 4，r 为 2:

lst = 'ABCD'
result = list(itertools.combinations(lst, len(lst)/2))
print len(result)
6

以下是显示我遇到的问题的辅助函数:

def C(lst):
    l = list(itertools.combinations(sorted(lst), len(lst)/2))
    s = set(l)
    print 'actual', len(l), l
    print 'unique', len(s), list(s)

如果我从 iPython 运行它，我可以这样调用它:

In [41]: C('ABCD')
actual 6 [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]
unique 6 [('B', 'C'), ('C', 'D'), ('A', 'D'), ('A', 'B'), ('A', 'C'), ('B', 'D')]

In [42]: C('ABAB')
actual 6 [('A', 'A'), ('A', 'B'), ('A', 'B'), ('A', 'B'), ('A', 'B'), ('B', 'B')]
unique 3 [('A', 'B'), ('A', 'A'), ('B', 'B')]

In [43]: C('ABBB')
actual 6 [('A', 'B'), ('A', 'B'), ('A', 'B'), ('B', 'B'), ('B', 'B'), ('B', 'B')]
unique 2 [('A', 'B'), ('B', 'B')]

In [44]: C('AAAA')
actual 6 [('A', 'A'), ('A', 'A'), ('A', 'A'), ('A', 'A'), ('A', 'A'), ('A', 'A')]
unique 1 [('A', 'A')]

我想要得到的是如上所示的唯一计数，但是执行 combinations 然后 set 无法缩放。当 lst 的长度 n 变长时，它会随着组合越来越大而变慢。

有没有办法使用数学或 Python 技巧来解决计算唯一组合的问题？

Answer 1

这里有一些 Python 代码基于 this Math Forum article 中概述的生成函数方法.对于输入中出现的每个字母，我们创建一个多项式 1 + x + x^2 + ... + x^k，其中 k 是出现的次数字母出现。然后，我们将这些多项式相乘:生成的多项式的第 n 系数会告诉您长度 n 有多少种组合。

我们将多项式简单地表示为其(整数)系数的列表，第一个系数表示常数项，下一个系数表示 x 的系数，依此类推。我们需要能够将这些多项式相乘，所以这里有一个函数可以这样做:

def polymul(p, q):
    """
    Multiply two polynomials, represented as lists of coefficients.
    """
    r = [0]*(len(p) + len(q) - 1)
    for i, c in enumerate(p):
        for j, d in enumerate(q):
            r[i+j] += c*d
    return r

有了上面的内容，下面的函数计算组合的数量:

from collections import Counter
from functools import reduce

def ncombinations(it, k):
    """
    Number of combinations of length *k* of the elements of *it*.
    """
    counts = Counter(it).values()
    prod = reduce(polymul, [[1]*(count+1) for count in counts], [1])
    return prod[k] if k < len(prod) else 0

在你的例子上测试这个:

>>> ncombinations("abcd", 2)
6
>>> ncombinations("abab", 2)
3
>>> ncombinations("abbb", 2)
2
>>> ncombinations("aaaa", 2)
1

在一些更长的例子中，证明这种方法即使对于长输入也是可行的:

>>> ncombinations("abbccc", 3)  # the math forum example
6
>>> ncombinations("supercalifragilisticexpialidocious", 10)
334640
>>> from itertools import combinations  # double check ...
>>> len(set(combinations(sorted("supercalifragilisticexpialidocious"), 10)))
334640
>>> ncombinations("supercalifragilisticexpialidocious", 20)
1223225
>>> ncombinations("supercalifragilisticexpialidocious", 34)
1
>>> ncombinations("supercalifragilisticexpialidocious", 35)
0
>>> from string import printable
>>> ncombinations(printable, 50)  # len(printable)==100
100891344545564193334812497256
>>> from math import factorial
>>> factorial(100)//factorial(50)**2  # double check the result
100891344545564193334812497256
>>> ncombinations("abc"*100, 100)
5151
>>> factorial(102)//factorial(2)//factorial(100)  # double check (bars and stars)
5151