Fastest way to find unique combinations of list

Question

I'm trying to solve the general problem of getting the unique combinations from a list in Python

Mathematically from https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html I can see that the formula for the number of combinations is n!/r!(n-r)! where n is the length of the sequence and r is the number to choose.

As shown by the following python where n is 4 and r is 2:

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

The following is a helper function to show the issue I have:

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)

If I run this from iPython I can call it thus:

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')]

What I want to get is the unique count as shown above but doing a combinations and then set doesn't scale. As when the length of lst which is n gets longer it slows down as the combinations get greater and greater.

Is there a way of using math or Python tricks to to solve the issue of counting the unique combinations ?

Answer 1

Here's some Python code based on the generating function approach outlined in this Math Forum article. For each letter appearing in the input we create a polynomial 1 + x + x^2 + ... + x^k, where k is the number of times that the letter appears. We then multiply those polynomials together: the nth coefficient of the resulting polynomial then tells you how many combinations of length n there are.

We'll represent a polynomial simply as a list of its (integer) coefficients, with the first coefficient representing the constant term, the next coefficient representing the coefficient of x, and so on. We'll need to be able to multiply such polynomials, so here's a function for doing so:

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

With the above in hand, the following function computes the number of combinations:

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

Testing this on your examples:

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

And on some longer examples, demonstrating that this approach is feasible even for long-ish inputs:

>>> 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

Start with a regular recursive definition of combinations() but add a test to only recurse when the lead value at that level hasn't been used before:

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))

Answer 3

It seems that this is called a multiset combination. I've faced the same problem and finally came up rewriting a function from sympy (here).

Instead of passing your iterable to something like itertools.combinations(p, r), you pass collections.Counter(p).most_common() to the following function to directly retrieve distinct combinations. It's a lot faster than filtering all combinations and also memory safe!

def counter_combinations(g, n):
    if sum(v for k, v in g) < n or not n:
        yield []
    else:
        for i, (k, v) in enumerate(g):
            if v >= n:
                yield [k]*n
                v = n - 1
            for v in range(min(n, v), 0, -1):
                for j in counter_combinations(g[i + 1:], n - v):
                    rv = [k]*v + j
                    if len(rv) == n:
                        yield rv

Here is an example:

from collections import Counter

p = Counter('abracadabra').most_common()
print(p)
c = [_ for _ in counter_combinations(p, 4)]
print(c)
print(len(c))

Output:

[('a', 5), ('b', 2), ('r', 2), ('c', 1), ('d', 1)]
[['a', 'a', 'a', 'a'], ['a', 'a', 'a', 'b'], ['a', 'a', 'a', 'r'], ['a', 'a', 'a', 'c'], ['a', 'a', 'a', 'd'], ['a', 'a', 'b', 'b'], ['a', 'a', 'b', 'r'], ['a', 'a', 'b', 'c'], ['a', 'a', 'b', 'd'], ['a', 'a', 'r', 'r'], ['a', 'a', 'r', 'c'], ['a', 'a', 'r', 'd'], ['a', 'a', 'c', 'd'], ['a', 'b', 'b', 'r'], ['a', 'b', 'b', 'c'], ['a', 'b', 'b', 'd'], ['a', 'b', 'r', 'r'], ['a', 'b', 'r', 'c'], ['a', 'b', 'r', 'd'], ['a', 'b', 'c', 'd'], ['a', 'r', 'r', 'c'], ['a', 'r', 'r', 'd'], ['a', 'r', 'c', 'd'], ['b', 'b', 'r', 'r'], ['b', 'b', 'r', 'c'], ['b', 'b', 'r', 'd'], ['b', 'b', 'c', 'd'], ['b', 'r', 'r', 'c'], ['b', 'r', 'r', 'd'], ['b', 'r', 'c', 'd'], ['r', 'r', 'c', 'd']]
31