你应该基于 itertools.combinations 来构建你的解决方案，因为它会处理好排序问题；短路过滤相对容易解决。
递归解决方案
让我们快速回顾一下如何实现 combinations；最简单的方法是采用嵌套 for 循环的方式，并将其转换为递归风格：
def combinations(iterable, r):
pool = tuple(iterable)
for i in range(0, len(pool)):
for j in range(i + 1, len(pool)):
...
yield (i, j, ...)
转换为递归形式：
def combinations(iterable, r):
pool = tuple(iterable)
def inner(start, k, acc):
if k == r:
yield acc
else:
for i in range(start, len(pool)):
for t in inner(i + 1, k + 1, acc + (pool[i], )):
yield t
return inner(0, 0, ())
现在应用过滤器非常容易：
def combinations_filterfalse(predicate, iterable, r):
pool = tuple(iterable)
def inner(start, k, acc):
if predicate(acc):
return
elif k == r:
yield acc
else:
for i in range(start, len(pool)):
for t in inner(i + 1, k + 1, acc + (pool[i], )):
yield t
return inner(0, 0, ())
让我们来检查一下：
>>> list(combinations_filterfalse(lambda t: sum(t) % 2 == 1, range(5), 2))
[(0, 2), (0, 4), (2, 4)]
迭代解决方案
itertools.combinations 的实际实现在文档中列出了一个迭代循环：
def combinations(iterable, r):
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = 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
yield tuple(pool[i] for i in indices)
为了优雅地适应谓词，需要稍微重新排列循环：
def combinations_filterfalse(predicate, iterable, r):
pool = tuple(iterable)
n = len(pool)
if r > n or predicate(()):
return
elif r == 0:
yield ()
return
indices, i = range(r), 0
while True:
while indices[i] + r <= i + n:
t = tuple(pool[k] for k in indices[:i+1])
if predicate(t):
indices[i] += 1
elif len(t) == r:
yield t
indices[i] += 1
else:
indices[i+1] = indices[i] + 1
i += 1
if i == 0:
return
i -= 1
indices[i] += 1
再次检查：
>>> list(combinations_filterfalse(lambda t: sum(t) % 2 == 1, range(5), 2))
[(0, 2), (0, 4), (2, 4)]
>>> list(combinations_filterfalse(lambda t: t == (1, 4), range(5), 2))
[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]
>>> list(combinations_filterfalse(lambda t: t[-1] == 3, range(5), 2))
[(0, 1), (0, 2), (0, 4), (1, 2), (1, 4), (2, 4)]
>>> list(combinations_filterfalse(lambda t: False, range(5), 2))
[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
>>> list(combinations_filterfalse(lambda t: False, range(5), 0))
[()]
比较
事实证明，递归解决方案不仅更简单，而且速度更快：
In [33]: timeit list(combinations_filterfalse_rec(lambda t: False, range(20), 5))
10 loops, best of 3: 24.6 ms per loop
In [34]: timeit list(combinations_filterfalse_it(lambda t: False, range(20), 5))
10 loops, best of 3: 76.6 ms per loop
itertools.combinations不会重复元素。itertools.permutations执行的是你认为combinations应该执行的操作。combinations(range(4), 3) --> 012 013 023 123- GP89[list[0]，list[3]，list[2]]可以通过，但[list[2]，list[3]，list[0]]会失败吗？ - Stuartitertools.permutations，这是一个问题，因为顺序并不重要，所以测试了许多不需要测试的东西。itertools.combinations不会重复元素，但是会测试012和013，即使01再次导致失败，也会测试不需要测试的内容。 - ded