<p>如果有一种方法可以在O(1)中生成所有组合,那么您可以在O(r)中通过生成和过滤来实现这一点。假设<code>itertools.combinations</code>有一个O(1)<code>next</code>,那么最多可以跳过r-1值,所以最坏的情况是r-1乘以O(1),对吗?在</p>
<p>为了避免混淆,我不认为存在<code>combinations</code>的O(1)实现,因此这是<em>而不是</em>O(r)。但有没有什么可能是<em>的呢?我不确定。不管怎样</p>
<p>所以:</p>
<pre><code>def nonconsecutive_combinations(p, r):
def good(combo):
return not any(combo[i]+1 == combo[i+1] for i in range(len(combo)-1))
return filter(good, itertools.combinations(p, r))
r, n = 2, 4
print(list(nonconsecutive_combinations(range(1, n+1), r))
</code></pre>
<p>打印:</p>
^{pr2}$
<hr/>
<p><code>itertools</code>文档不能保证<code>combinations</code>有一个O(1)<code>next</code>。但在我看来,如果有一个可能的O(1)算法,他们会使用它,如果没有,你就找不到。在</p>
<p>你可以读<a href="http://hg.python.org/cpython/file/3.3/Modules/itertoolsmodule.c#l2289" rel="nofollow">the source code</a>,或者我们可以计时……但是我们要做的是,让我们来计时。在</p>
<p><a href="http://pastebin.com/ydk1TMbD" rel="nofollow">http://pastebin.com/ydk1TMbD</a>有我的代码、thkang的代码和一个测试驱动程序。它的打印次数是迭代整个序列的成本除以序列的长度。在</p>
<p>当<code>n</code>从4到20,而<code>r</code>固定为2,我们可以看到两者的时间都在下降。(记住,迭代序列的总时间当然在增加。它只是<code>the total length</code>)中的次线性,<code>n</code>范围从7到20,<code>r</code>固定在4,这也是正确的。在</p>
<p>当<code>n</code>固定为12,而<code>r</code>的范围为2到5,两者的时间从2到5线性增加,但是1和6的时间远高于预期。在</p>
<p>仔细想想,924个值中只有6个是好值,对吧?这就是为什么每<code>next</code>的时间会随着<code>n</code>的上升而下降。总的时间在增加,但是产生的价值的数量增长得更快。在</p>
<p>所以,<code>combinations</code>没有O(1)<code>next</code>;它有一些复杂的东西。我的算法没有O(r)<code>next</code>;这也是一个复杂的问题。我认为在整个迭代过程中指定性能保证比按<code>next</code>要容易得多(如果知道如何计算,就很容易除以值的数目)。在</p>
<p>无论如何,我测试的两种算法的性能特征完全相同。(奇怪的是,将包装器<code>return</code>转换为<code>yield from</code>使得递归的更快,过滤的慢……但是无论如何,这是一个小的常量因子,谁在乎呢?)在</p>