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)