<p>这是我的递归生成器(如果选择了<code>n</code>第个项,它将跳过第<code>n+1</code>项):</p>
<pre><code>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]]
</code></pre>
<p>关于效率:</p>
<p>这段代码不能是O(1),因为遍历堆栈并在每次迭代上构建新的集合将不是O(1)。同样,递归生成器意味着您必须使用<code>r</code>最大堆栈深度来获得<code>r</code>项组合。这意味着对于低<code>r</code>,调用堆栈的成本可能比非递归生成更昂贵。有足够的<code>n</code>和{<cd3>},它可能比基于itertools的解决方案更有效。在</p>
<p>我在这个问题中测试了两个上传的代码:</p>
^{pr2}$
<p>结果和更多结果(编辑)(在windows7上,python 64位2.7.3,带8gb ram的core i5 ivy bridge):</p>
<pre><code>(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
</code></pre>
<p>如您所见,<strike>递归解与itertools.组合当<code>n</code>向上</strike>时,基于的解决方案会变得更宽。在</p>
<p>事实上,由于两个解决方案之间的差距很大程度上依赖于<code>r</code>-更大的<code>r</code>意味着你必须扔掉从<code>itertools.combinations</code>生成的更多组合。例如,在<code>n=20, r=9</code>的情况下:我们在167960(20C9)个组合中过滤并只获取220个组合。如果<code>n</code>和{<cd3>}都很小,那么使用<code>itertools.combinations</code>会更快,因为它在更少的r下效率更高,而且不会像我解释的那样使用堆栈。(如您所见,itertools是非常优化的(如果用<code>for</code>、<code>if</code>、<code>while</code>和一堆生成器和列表理解编写逻辑,它不会像itertools抽象的那样快),这也是人们喜欢python的原因之一——你把代码带到了更高的层次,你就会得到回报。没有多少语言能做到这一点。在</p>