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

Question

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

在数学上从https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html我可以看到,对于组合的数量的公式是n!/r!(n-r)!其中n是序列的长度和r是选择的数量.

如下面的python所示,其中n4 r是2 并且是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')]

我想得到的是如上所示的唯一计数,但做了a combinations然后set不进行缩放.当长度lst这是n变长的组合获得越来越大的它会减慢.

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

Answer 1

下面是一些基于此数学论坛文章中概述的生成函数方法的 Python 代码。对于输入中出现的每个字母，我们创建一个多项式1 + x + x^2 + ... + x^k，其中k是字母出现的次数。然后我们将这些多项式相乘：n结果多项式的第 th 个系数告诉您有多少种长度组合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

Answer 2

从组合（）的常规递归定义开始，但添加一个测试以仅在之前未使用该级别的领先值时进行递归：

def uniq_comb(pool, r):
    """ Return an iterator over a all distinct r-length
    combinations taken from a pool of values that
    may contain duplicates.

    Unlike itertools.combinations(), element uniqueness
    is determined by value rather than by position.

    """
    if r:
        seen = set()
        for i, item in enumerate(pool):
            if item not in seen:
                seen.add(item)
                for tail in uniq_comb(pool[i+1:], r-1):
                    yield (item,) + tail
    else:
        yield ()

if __name__ == '__main__':
    from itertools import combinations

    pool = 'ABRACADABRA'
    for r in range(len(pool) + 1):
        assert set(uniq_comb(pool, r)) == set(combinations(pool, r))
        assert dict.fromkeys(uniq_comb(pool, r)) == dict.fromkeys(combinations(pool, r))