Remove combinations that contains some values before even calculated

Question

given a list and exclusions elements, is it possible to ignore calculation of combinations that contains these elements ?

Example 1

Given l = [1, 2, 3, 4, 5], I want to calculate all combinations of size 4 and excluding combinations that contains (1, 3) before even calculated.

The results would be :

    All results:            Wanted results:

    [1, 2, 3, 4]            [1, 2, 4, 5]
    [1, 2, 3, 5]            [2, 3, 4, 5]
    [1, 2, 4, 5]
    [1, 3, 4, 5]
    [2, 3, 4, 5]

All combinations that contained 1 and 3 have been removed.

Example 2

suggested by @Eric Duminil

the result for l = [1, 2, 3, 4, 5, 6], size 4 and

• excluding (1, 2, 3) in second column

• excluding (1, 2) in third column

  All results:        Wanted results 1            Wanted results 2
                      (Excluding [1, 2, 3]):      (Excluding [1, 2])
  
  [1, 2, 3, 4]        [1, 2, 4, 5]                [1, 3, 4, 5]
  [1, 2, 3, 5]        [1, 2, 4, 6]                [1, 3, 4, 6]
  [1, 2, 3, 6]        [1, 2, 5, 6]                [1, 3, 5, 6]
  [1, 2, 4, 5]        [1, 3, 4, 5]                [1, 4, 5, 6]
  [1, 2, 4, 6]        [1, 3, 4, 6]                [2, 3, 4, 5]
  [1, 2, 5, 6]        [1, 3, 5, 6]                [2, 3, 4, 6]
  [1, 3, 4, 5]        [1, 4, 5, 6]                [2, 3, 5, 6]
  [1, 3, 4, 6]        [2, 3, 4, 5]                [2, 4, 5, 6]
  [1, 3, 5, 6]        [2, 3, 4, 6]                [3, 4, 5, 6]
  [1, 4, 5, 6]        [2, 3, 5, 6]                                
  [2, 3, 4, 5]        [2, 4, 5, 6]                                
  [2, 3, 4, 6]        [3, 4, 5, 6]                                
  [2, 3, 5, 6]           
  [2, 4, 5, 6]           
  [3, 4, 5, 6]        
  

All combinations that contained 1 and 2 and 3 have been removed from wanted results 1

All combinations that contained 1 and 2 have been removed from wanted results 2

I have a much bigger combinations to compute but it takes a lot of time and I want to reduce this time using these exclusions.

Tried solutions

With method 1, the combinations are still calculated

With method 2, I tried to modify the combinations function but I could not find a proper way to ignore my exclusion list before calculated.

            Method 1                    |               Method 2
                                        |               
def main():                             |   def combinations(iterable, r):
    l = list(range(1, 6))               |       pool = tuple(iterable)
    comb = combinations(l, 4)           |       n = len(pool)
                                        |       if r > n:
    for i in comb:                      |           return
        if set([1, 3]).issubset(i):     |       indices = list(range(r))
            continue                    |       yield tuple(pool[i] for i in indices)
        else                            |       while True:
            process()                   |           for i in reversed(range(r)):
                                        |               if indices[i] != i + n - r:
                                        |                   break
                                        |               else:
                                        |                   return
                                        |           indices[i] += 1
                                        |           for j in range(i+1, r):
                                        |               indices[j] = indices[j-1] + 1
                                        |           yield tuple(pool[i] for i in indices)

EDIT:

First of all, thank you all for your help, I forgot to give more details about constraints.

• The order of the ouputs is not relevant, from example, if result is [1, 2, 4, 5] [2, 3, 4, 5] or [2, 3, 4, 5] [1, 2, 4, 5], it is not important.

• The elements of the combinations should be (if possible) sorted, [1, 2, 4, 5] [2, 3, 4, 5] and not [2, 1, 5, 4] [3, 2, 4, 5] but it is not important since the combinations could be sorted after.

• The exclusions list is a list of all items that should not appear in the combinations together. e.g If my exclusion list is (1, 2, 3), all combinations that contains 1 and 2 and 3 should not be calculated. However, combinations with 1 and 2 and not 3 are allowed. In that case, if I exclude combinations that contains (1, 2) and (1, 2, 3) it is completely useless since all combinations that will be filtered by (1, 2, 3) are already filtered by (1, 2)

• Multiple exclude lists must be possible because I use multiple constraints on my combinations.

Tested answers

@tobias_k This solution considers the exclusion list (1, 2, 3) as OR exclusion meaning (1, 2), (2, 3) and (1, 3) will be excluded if I understood well, this is useful in a case but not in my current problem, I modified the question to give more details, sorry for confusion. In your answer, I can't use only lists (1, 2) and (1, 3) as exclusion as you specified it. However the big advantage of this solution is to permit multiple exclusions.

@Kasramvd and @mikuszefski Your solution is really close to what I want, if it does include multiple exclusion lists, it would be the answer.

Thanks

Answer 1

(Turns out this does not do exactly what OP wants. Still leaving this here as it might help others.)

---

To include mutually exclusive elements, you could wrap those in lists within the list, get the combinations of those, and then the product of the combinations of sub-lists:

>>> from itertools import combinations, product
>>> l = [[1, 3], [2], [4], [5]]
>>> [c for c in combinations(l, 4)]
[([1, 3], [2], [4], [5])]
>>> [p for c in combinations(l, 4) for p in product(*c)]
[(1, 2, 4, 5), (3, 2, 4, 5)]

A more complex example:

>>> l = [[1, 3], [2, 4, 5], [6], [7]]
>>> [c for c in combinations(l, 3)]
[([1, 3], [2, 4, 5], [6]),
 ([1, 3], [2, 4, 5], [7]),
 ([1, 3], [6], [7]),
 ([2, 4, 5], [6], [7])]
>>> [p for c in combinations(l, 3) for p in product(*c)]
[(1, 2, 6),
 (1, 4, 6),
 ... 13 more ...
 (4, 6, 7),
 (5, 6, 7)]

This does not generate any "junk" combinations to be filtered out afterwards. However, it assumes that you want at most one element from each "exclusive" group, e.g. in the second example, it not only prevents combinations with 2,4,5, but also those with 2,4, 4,5, or 2,5. Also, it is not possible (or at least not easy) to have exclusively one of 1,3, and 1,5, but allow for 3,5. (It might be possible to extend it to those cases, but I'm not yet sure if and how.)

---

You can wrap this in a function, deriving the slightly different input format from your (presumed) format and returning an accordant generator expression. Here, lst is the list of elements, r the number of items per combinations, and exclude_groups a list of groups of mutually-exclusive elements:

from itertools import combinations, product

def comb_with_excludes(lst, r, exclude_groups):
    ex_set = {e for es in exclude_groups for e in es}
    tmp = exclude_groups + [[x] for x in lst if x not in ex_set]
    return (p for c in combinations(tmp, r) for p in product(*c))

lst = [1, 2, 3, 4, 5, 6, 7]
excludes = [[1, 3], [2, 4, 5]]
for x in comb_with_excludes(lst, 3, excludes):
    print(x)

Answer 2

From an algorithmic perspective you can separate the excluded and the reset of the valid items and calculate the combinations of each set separately and just concatenate the result based on the desire length. This approach will entirely refuse of including all the excluded items at once in combination but will omit the actual order.

from itertools import combinations

def comb_with_exclude(iterable, comb_num, excludes):
    iterable = tuple(iterable)
    ex_len = len(excludes)
    n = len(iterable)

    if comb_num < ex_len or comb_num > n:
        yield from combinations(iterable, comb_num)

    else:
        rest = [i for i in iterable if not i in excludes]
        ex_comb_rang = range(0, ex_len)
        rest_comb_range = range(comb_num, comb_num - ex_len, -1)
        # sum of these pairs is equal to the comb_num
        pairs = zip(ex_comb_rang, rest_comb_range)

        for i, j in pairs:
            for p in combinations(excludes, i):
                for k in combinations(rest, j):
                    yield k + p
       """
       Note that instead of those nested loops you could wrap the combinations within a product function like following:
       for p, k in product(combinations(excludes, i), combinations(rest, j)):
            yield k + p
       """

Demo:

l = [1, 2, 3, 4, 5, 6, 7, 8]
ex = [2, 5, 6]
print(list(comb_with_exclude(l, 6, ex)))

[(1, 3, 4, 7, 8, 2), (1, 3, 4, 7, 8, 5), (1, 3, 4, 7, 8, 6), (1, 3, 4, 7, 2, 5), (1, 3, 4, 8, 2, 5), (1, 3, 7, 8, 2, 5), (1, 4, 7, 8, 2, 5), (3, 4, 7, 8, 2, 5), (1, 3, 4, 7, 2, 6), (1, 3, 4, 8, 2, 6), (1, 3, 7, 8, 2, 6), (1, 4, 7, 8, 2, 6), (3, 4, 7, 8, 2, 6), (1, 3, 4, 7, 5, 6), (1, 3, 4, 8, 5, 6), (1, 3, 7, 8, 5, 6), (1, 4, 7, 8, 5, 6), (3, 4, 7, 8, 5, 6)]

l = [1, 2, 3, 4, 5]
ex = [1, 3]
print(list(comb_with_exclude(l, 4, ex)))

[(2, 4, 5, 1), (2, 4, 5, 3)]

Benckmark with other answers:

Results: this approach is faster that the others

# this answer
In [169]: %timeit list(comb_with_exclude(lst, 3, excludes[0]))
100000 loops, best of 3: 6.47 µs per loop

# tobias_k
In [158]: %timeit list(comb_with_excludes(lst, 3, excludes))
100000 loops, best of 3: 13.1 µs per loop

# Vikas Damodar
In [166]: %timeit list(combinations_exc(lst, 3))
10000 loops, best of 3: 148 µs per loop

# mikuszefski
In [168]: %timeit list(sub_without(lst, 3, excludes[0]))
100000 loops, best of 3: 12.52 µs per loop

Answer 3

(As it turned out that my previous answer does not really satisfy the constraints of the question, here's another one. I'm posting this as a separate answer, as the approach is vastly different and the original answer may still help others.)

You can implement this recursively, each time before recursing to add another element to the combinations checking whether that would violate one of the exclude-sets. This does not generate and invalid combinations, and it works with overlapping exclude-sets (like (1,3), (1,5)), and exclude-sets with more than two elements (like (2,4,5), allowing any combinations except all of them together).

def comb_with_excludes(lst, n, excludes, i=0, taken=()):
    if n == 0:
        yield taken  # no more needed
    elif i <= len(lst) - n:
        t2 = taken + (lst[i],)  # add current element
        if not any(e.issubset(t2) for e in excludes):
            yield from comb_with_excludes(lst, n-1, excludes, i+1, t2)
        if i < len(lst) - n:  # skip current element
            yield from comb_with_excludes(lst, n, excludes, i+1, taken)

Example:

>>> lst = [1, 2, 3, 4, 5, 6]
>>> excludes = [{1, 3}, {1, 5}, {2, 4, 5}]
>>> list(comb_with_excludes(lst, 4, excludes))
[[1, 2, 4, 6], [2, 3, 4, 6], [2, 3, 5, 6], [3, 4, 5, 6]]

---

Well, I did time it now, and it turns out this is considerably slower than naively using itertools.combination in a generator expression with a filter, much like you already do:

def comb_naive(lst, r, excludes):
    return (comb for comb in itertools.combinations(lst, r)
                 if not any(e.issubset(comb) for e in excludes))

Calculating the combinations in Python is just slower than using the library (which is probably implemented in C) and filtering the results afterwards. Depending on the amount of combinations that can be excluded, this might be faster in some cases, but to be honest, I have my doubts.

You could get better results if you can use itertools.combinations for subproblems, as in Kasramvd's answer, but for multiple, non-disjunct exclude sets that's more difficult. One way might be to separate the elements in the list into two sets: Those that have constraints, and those that don't. Then, use itertoolc.combinations for both, but check the constraints only for the combinations of those elements where they matter. You still have to check and filter the results, but only a part of them. (One caveat, though: The results are not generated in order, and the order of the elements within the yielded combinations is somewhat messed up, too.)

def comb_with_excludes2(lst, n, excludes):
    wout_const = [x for x in lst if not any(x in e for e in excludes)]
    with_const = [x for x in lst if     any(x in e for e in excludes)]
    k_min, k_max = max(0, n - len(wout_const)), min(n, len(with_const))
    return (c1 + c2 for k in range(k_min, k_max)
                    for c1 in itertools.combinations(with_const, k)
                    if not any(e.issubset(c1) for e in excludes)
                    for c2 in itertools.combinations(wout_const, n - k))

This is already much better then the recursive pure-Python solution, but still not as good as the "naive" approach for the above example:

>>> lst = [1, 2, 3, 4, 5, 6]
>>> excludes = [{1, 3}, {1, 5}, {2, 4, 5}]
>>> %timeit list(comb_with_excludes(lst, 4, excludes))
10000 loops, best of 3: 42.3 µs per loop
>>> %timeit list(comb_with_excludes2(lst, 4, excludes))
10000 loops, best of 3: 22.6 µs per loop
>>> %timeit list(comb_naive(lst, 4, excludes))
10000 loops, best of 3: 16.4 µs per loop

However, the results depend very much on the input. For a larger list, with constraints only applying to a few of those elements, this approach is in fact faster then the naive one:

>>> lst = list(range(20))
>>> %timeit list(comb_with_excludes(lst, 4, excludes))
10 loops, best of 3: 15.1 ms per loop
>>> %timeit list(comb_with_excludes2(lst, 4, excludes))
1000 loops, best of 3: 558 µs per loop
>>> %timeit list(comb_naive(lst, 4, excludes))
100 loops, best of 3: 5.9 ms per loop

Answer 4

I have made an attempt to edit combinations according to your requirements :

def combinations(iterable, r):
   # combinations('ABCD', 2) --> AB AC AD BC BD CD
   # combinations(range(4), 3) --> 012 013 023 123
   pool = tuple(iterable)
   n = len(pool)
   if r > n:
      return
   indices = list(range(r))
   # yield tuple(pool[i] for i in indices)
   while True:
       for i in reversed(range(r)):
           if indices[i] != i + n - r:
               break
    else:
        return
    indices[i] += 1
    for j in range(i+1, r):
        indices[j] = indices[j-1] + 1
    # print(tuple(pool[i] for i in indices ), "hai")
    if 1 in tuple(pool[i] for i in indices ) and 3  in tuple(pool[i] for i in indices ):
        pass
    else:
        yield tuple(pool[i] for i in indices)


d = combinations(list(range(1, 6)),4)
for i in d:
   print(i)

It will return something like this :

(1, 2, 4, 5) (2, 3, 4, 5)

Answer 5

I did the exclusion during the combination using the following code to save the second loop time. you just need to pass the indices of the excluded elements as a set.

update: working fiddle

from itertools import permutations

def combinations(iterable, r, combIndeciesExclusions=set()):
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if ( len(combIndeciesExclusions)==0 or not combIndeciesExclusions.issubset(indices)) and sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)


l = list(range(1, 6))
comb = combinations(l, 4, set([0,2]))
print list(comb)

Answer 6

I guess my answer is similar to some others here, but this was what I fiddled together in parallel

from itertools import combinations, product

"""
with help from
https://stackoverflow.com/questions/374626/how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements
https://stackoverflow.com/questions/32438350/python-merging-two-lists-with-all-possible-permutations
https://stackoverflow.com/questions/952914/making-a-flat-list-out-of-list-of-lists-in-python
"""
def sub_without( S, m, forbidden ):
    out = []
    allowed = [ s for s in S if s not in forbidden ]
    N = len( allowed )
    for k in range( len( forbidden ) ):
        addon = [ list( x ) for x in combinations( forbidden, k) ]
        if N + k >= m:
            base = [ list( x ) for x in combinations( allowed, m - k ) ]
            leveltotal = [ [ item for sublist in x for item in sublist ] for x in product( base, addon ) ]
            out += leveltotal
    return out

val = sub_without( range(6), 4, [ 1, 3, 5 ] )

for x in val:
    print sorted(x)

>>
[0, 1, 2, 4]
[0, 2, 3, 4]
[0, 2, 4, 5]
[0, 1, 2, 3]
[0, 1, 2, 5]
[0, 2, 3, 5]
[0, 1, 3, 4]
[0, 1, 4, 5]
[0, 3, 4, 5]
[1, 2, 3, 4]
[1, 2, 4, 5]
[2, 3, 4, 5]

Answer 7

Algorithmically you have to calculate the combination of the items within your list that are not among the excluded ones then add the respective combinations of the excluded items to the combination of the rest of items. This approach of course requires a lot of checking and need to keep track of the indexes which even if you do it in python it won't give you a notable difference in performance (known as drawbacks of Constraint satisfaction problem). (rather than just calculating them using combination and filtering the unwanted items out).

Therefor, I think this is the best way to go in most of the cases:

In [77]: from itertools import combinations, filterfalse

In [78]: list(filterfalse({1, 3}.issubset, combinations(l, 4)))
Out[78]: [(1, 2, 4, 5), (2, 3, 4, 5)]