n+1这是我的递归生成器（如果选择了第一项，它只会跳过第一项n）：
def non_consecutive_combinator(rnge, r, prev=[]):
if r == 0:
yield prev
else:
for i, item in enumerate(rnge):
for next_comb in non_consecutive_combinator(rnge[i+2:], r-1, prev+[item]):
yield next_comb
print list(non_consecutive_combinator([1,2,3,4], 2))
#[[1, 3], [1, 4], [2, 4]]
print list(non_consecutive_combinator([1,2,3,4,5], 2))
#[[1, 3], [1, 4], [1, 5], [2, 4], [2, 5], [3, 5]]
print list(non_consecutive_combinator(range(1, 10), 3))
#[[1, 3, 5], [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 3, 9], [1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 8], [1, 6, 9], [1, 7, 9], [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 8], [2, 6, 9], [2, 7, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 8], [3, 6, 9], [3, 7, 9], [4, 6, 8], [4, 6, 9], [4, 7, 9], [5, 7, 9]]
关于效率：
此代码不可能是 O(1)，因为遍历堆栈并在每次迭代时构建一个新集合不会是 O(1)。此外，递归生成器意味着您必须使用r最大堆栈深度来获得r-item 组合。这意味着使用低r，调用堆栈的成本可能比非递归生成更昂贵。有了足够的nand r，它可能比基于 itertools 的解决方案更有效。
我在这个问题中测试了两个上传的代码：
from itertools import ifilter, combinations
import timeit
def filtered_combi(n, r):
def good(combo):
return not any(combo[i]+1 == combo[i+1] for i in range(len(combo)-1))
return ifilter(good, combinations(range(1, n+1), r))
def non_consecutive_combinator(rnge, r, prev=[]):
if r == 0:
yield prev
else:
for i, item in enumerate(rnge):
for next_comb in non_consecutive_combinator(rnge[i+2:], r-1, prev+[item]):
yield next_comb
def wrapper(n, r):
return non_consecutive_combinator(range(1, n+1), r)
def consume(f, *args, **kwargs):
deque(f(*args, **kwargs))
t = timeit.timeit(lambda : consume(wrapper, 30, 4), number=100)
f = timeit.timeit(lambda : consume(filtered_combi, 30, 4), number=100)
结果和更多结果（编辑）（在 windows7，python 64bit 2.7.3，核心 i5 ivy 桥与 8gb ram）：
(n, r) recursive itertools
----------------------------------------
(30, 4) 1.6728046 4.0149797 100 times 17550 combinations
(20, 4) 2.6734657 7.0835997 1000 times 2380 combinations
(10, 4) 0.1253318 0.3157737 1000 times 35 combinations
(4, 2) 0.0091073 0.0120918 1000 times 3 combinations
(20, 5) 0.6275073 2.4236898 100 times 4368 combinations
(20, 6) 1.0542227 6.1903468 100 times 5005 combinations
(20, 7) 1.3339530 12.4065561 100 times 3432 combinations
(20, 8) 1.4118724 19.9793801 100 times 1287 combinations
(20, 9) 1.4116702 26.1977839 100 times 220 combinations
如您所见，递归解决方案和基于 itertools.combination 的解决方案之间的差距随着n上升而变大。
实际上，两种解决方案之间的差距在很大程度上取决于r- 更大r意味着您必须丢弃更多从itertools.combinations. 例如，在以下情况下n=20, r=9：我们过滤并在 167960(20C9) 个组合中仅取 220 个组合。如果n和r很小，使用itertools.combinations会更快，因为它在更少的 r 下效率更高，并且不使用堆栈，正如我解释的那样。（如您所见，itertools 非常优化（如果使用 、 和一堆生成器和列表推导编写逻辑for，if它while不会像使用 itertools 抽象的那样快），这是人们为什么喜欢python——你把你的代码提升到更高的水平，你会得到回报。这方面的语言不多。