Sye*_*lec 18 python combinations python-itertools python-3.x
给定列表和排除元素,是否可以忽略包含这些元素的组合的计算？
鉴于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的所有组合.
由@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,我尝试修改组合函数,但在计算之前找不到合适的方法来忽略我的排除列表.
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和2和3的所有组合.但是,允许使用1和2而不是3的组合.在这种情况下,如果我排除包含的组合(1, 2)并且(1, 2, 3)它完全无用,因为将过滤的所有组合(1, 2, 3)都已经过滤(1, 2)
必须有多个排除列表,因为我对我的组合使用了多个约束.
@tobias_k此解决方案将排除列表(1, 2, 3)视为OR排除意义(1, 2), (2, 3) and (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)
（事实证明，我之前的答案并没有真正满足问题的约束，这是另一个答案。我将其作为单独的答案发布，因为方法有很大不同，原始答案可能仍然有帮助其他的。）
\n\n您可以递归地实现此操作，每次在递归之前将另一个元素添加到组合中，检查是否会违反其中一个排除集。这不会生成无效的组合，并且它适用于重叠的排除集（例如(1,3), (1,5)）和具有两个以上元素的排除集（例如(2,4,5)，允许除所有组合之外的任何组合）。
def comb_with_excludes(lst, n, excludes, i=0, taken=()):\n if n == 0:\n yield taken # no more needed\n elif i <= len(lst) - n:\n t2 = taken + (lst[i],) # add current element\n if not any(e.issubset(t2) for e in excludes):\n yield from comb_with_excludes(lst, n-1, excludes, i+1, t2)\n if i < len(lst) - n: # skip current element\n yield from comb_with_excludes(lst, n, excludes, i+1, taken)\n例子：
\n\n>>> lst = [1, 2, 3, 4, 5, 6]\n>>> excludes = [{1, 3}, {1, 5}, {2, 4, 5}]\n>>> list(comb_with_excludes(lst, 4, excludes))\n[[1, 2, 4, 6], [2, 3, 4, 6], [2, 3, 5, 6], [3, 4, 5, 6]]\n好吧，我现在对它进行了计时，结果发现这比天真地itertools.combination在带有过滤器的生成器表达式中使用要慢得多，就像您已经做的那样：
def comb_naive(lst, r, excludes):\n return (comb for comb in itertools.combinations(lst, r)\n if not any(e.issubset(comb) for e in excludes))\n在 Python 中计算组合只是比使用库（可能是用 C 实现）并随后过滤结果慢。根据可以排除的组合数量，在某些情况下这可能会更快，但说实话，我对此表示怀疑。
\n\n如果您可以用于子问题，您可以获得更好的结果itertools.combinations，如Kasramvd 的答案，但对于多个非分离的排除集则更困难。一种方法可能是将列表中的元素分成两组：有约束的元素和没有约束的元素。然后，使用itertoolc.combinations两者，但仅检查重要元素的组合的约束。您仍然需要检查和过滤结果，但只是其中的一部分。（不过，需要注意的是：结果不是按顺序生成的，并且生成的组合中元素的顺序也有些混乱。）
def comb_with_excludes2(lst, n, excludes):\n wout_const = [x for x in lst if not any(x in e for e in excludes)]\n with_const = [x for x in lst if any(x in e for e in excludes)]\n k_min, k_max = max(0, n - len(wout_const)), min(n, len(with_const))\n return (c1 + c2 for k in range(k_min, k_max)\n for c1 in itertools.combinations(with_const, k)\n if not any(e.issubset(c1) for e in excludes)\n for c2 in itertools.combinations(wout_const, n - k))\n这已经比递归纯 Python 解决方案好得多，但仍然不如上面示例的“天真的”方法：
\n\n>>> lst = [1, 2, 3, 4, 5, 6]\n>>> excludes = [{1, 3}, {1, 5}, {2, 4, 5}]\n>>> %timeit list(comb_with_excludes(lst, 4, excludes))\n10000 loops, best of 3: 42.3 \xc2\xb5s per loop\n>>> %timeit list(comb_with_excludes2(lst, 4, excludes))\n10000 loops, best of 3: 22.6 \xc2\xb5s per loop\n>>> %timeit list(comb_naive(lst, 4, excludes))\n10000 loops, best of 3: 16.4 \xc2\xb5s per loop\n然而，结果很大程度上取决于输入。对于较大的列表，约束仅适用于其中的一些元素，这种方法实际上比简单的方法更快：
\n\n>>> lst = list(range(20))\n>>> %timeit list(comb_with_excludes(lst, 4, excludes))\n10 loops, best of 3: 15.1 ms per loop\n>>> %timeit list(comb_with_excludes2(lst, 4, excludes))\n1000 loops, best of 3: 558 \xc2\xb5s per loop\n>>> %timeit list(comb_naive(lst, 4, excludes))\n100 loops, best of 3: 5.9 ms per loop\n| 归档时间： |
|
| 查看次数： |
1805 次 |
| 最近记录： |