给定一个列表和排除元素，是否可以忽略包含这些元素的组合计算？

示例 1

给定 l = [1, 2, 3, 4, 5]，我想计算 size 4 的所有组合，不包括包含 ( 1, 3) 甚至在计算之前。

结果是:

    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]

所有包含 1 和 3 的组合均已删除。

示例 2

@Eric Duminil 建议

l = [1, 2, 3, 4, 5, 6]、size 4 和

• 不包括第二列中的(1, 2, 3)

• 不包括第三列的(1, 2)

  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]        
  

所有包含 1 和 2 和 3 的组合都已从想要的结果 1 中删除

所有包含 1 和 2 的组合都已从想要的结果 2 中删除

我有更大的组合要计算，但这需要很多时间，我想使用这些排除项来减少这个时间。

尝试过的解决方案

使用方法1，仍然计算组合

使用方法2，我尝试修改combinations function但我找不到合适的方法在计算之前忽略我的排除列表。

            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)

编辑:

首先，谢谢大家的帮助，我忘了提供更多关于约束的细节。

• 输出的顺序不相关，例如，如果结果是 [1, 2, 4, 5] [2, 3, 4, 5] 或 [2, 3, 4, 5] [1, 2, 4, 5]，不重要。

• 组合的元素应该(如果可能)排序，[1, 2, 4, 5] [2, 3, 4, 5] 而不是 [ 2, 1, 5, 4] [3, 2, 4, 5] 但这并不重要，因为可以对组合进行排序。

• 排除列表是不应出现组合一起的所有项目的列表。例如，如果我的排除列表是 (1, 2, 3)，则不应计算包含 1 and 2 and 3 的所有组合。但是，允许使用 1 和 2 而不是 3 的组合。在这种情况下，如果我排除包含 (1, 2) 和 (1, 2, 3) 的组合，它完全没用，因为所有组合都将被 (1, 2, 3) 已经被 (1, 2)

过滤

• 多个排除列表必须是可能的，因为我对我的组合使用了多个约束。

测试答案

@tobias_k 此解决方案将排除列表 (1, 2, 3) 视为 OR 排除意味着 (1, 2), (2, 3) 和 (1, 3) 将是如果我理解得很好，则排除在外，这在一个案例中很有用，但在我当前的问题中没有，我修改了问题以提供更多细节，抱歉造成混淆。在您的回答中，我不能仅使用列表 (1, 2) 和 (1, 3) 作为您指定的排除项。然而，这种解决方案的一大优势是允许多重排除。

@Kasramvd 和 @mikuszefski 您的解决方案非常接近我想要的，如果它确实包含多个排除列表，那就是答案。

谢谢

最佳答案

(事实证明这并不完全符合 OP 的要求。仍然将其留在这里，因为它可能对其他人有所帮助。)

要包含互斥元素，您可以将它们包装在列表中的列表中，获取 combinations其中，然后是 product子列表的组合:

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

一个更复杂的例子:

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

这不会生成任何以后要过滤掉的“垃圾”组合。但是，它假定您最多需要每个“独占”组中的一个元素，例如在第二个示例中，它不仅阻止与 2,4,5 的组合，还阻止与 2,4、4,5 的组合，或 2,5。此外，不可能(或至少不容易)只拥有 1,3 和 1,5 之一，但允许 3,5 。 (也许可以将其扩展到这些情况，但我还不确定是否以及如何。)

您可以将其包装在一个函数中，从您的(假定的)格式派生出稍微不同的输入格式并返回一个一致的生成器表达式。这里，lst 是元素列表，r 是每个组合的项目数，exclude_groups 是互斥元素组的列表:

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)

关于python - 在计算之前删除包含某些值的组合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48616694/