<p>这很有趣!这个怎么样:</p>
<pre><code>def nonconsecutive_combinations(r, n):
# first combination, startng at 1, step-size 2
combination = range(1, r*2, 2)
# as long as all items are less than or equal to n
while combination[r-1] <= n:
yield tuple(combination)
p = r-1 # pointer to the element we will increment
a = 1 # number that will be added to the last element
# find the rightmost element we can increment without
# making the last element bigger than n
while p > 0 and combination[p] + a > n:
p -= 1
a += 2
# increment the item and
# fill the tail of the list with increments of two
combination[p:] = range(combination[p]+1, combination[p] + 2*(r-p), 2)
</code></pre>
<p>每个<code>next()</code>调用都应该有一个O(r)。。
我在考虑如何将其转换为自然数时产生了这个想法,但花了相当长的时间才把细节弄好。在</p>
^{pr2}$
<h2>我来解释一下这是怎么回事</h2>
<p>包含<code>r</code>元素的元组<code>c</code>是结果集的一部分的条件:</p>
<ol>
<li>元组中的任何元素至少与前面的元素加2一样大。
(<code>c[x] >= c[x-1] + 2</code>)</li>
<li>所有元素都小于或等于<code>n</code>。
因为1。可以说最后一个元素小于
或等于<code>n</code>。(<code>c[r-1] <= n</code>)</li>
</ol>
<p><em>可以</em>成为结果集一部分的最小元组是<code>(1, 3, 5, ..., 2*r-1)</code>。
当我说一个元组比另一个“小”时,我假设的是字典顺序。在</p>
<p>正如Blckknght指出的,即使是最小的元组也可能太大,以满足条件2。在</p>
<p>上面的函数包含两个while循环:</p>
<ul>
<li><p>外循环逐步遍历结果,并假设它们按字典顺序出现并满足条件1。一旦有问题的元组违反了条件2,我们就知道我们已经用尽了结果集并完成了:</p>
<pre><code>combination = range(1, r*2, 2)
while combination[r-1] <= n:
</code></pre>
<p>第一行根据条件1用第一个可能的结果初始化结果元组。第二行直接转换为条件二。</p></li>
<li><p>内部循环查找满足条件1的下一个可能的元组。在</p>
<pre><code>yield tuple(combination)
</code></pre>
<p>由于<code>while</code>条件(2)为真,并且我们确保结果满足条件1,所以我们可以生成当前的结果元组。在</p>
<p>下一步,为了找到字典形式的下一个元组,我们将在最后一个元素中添加“1”。在</p>
<pre><code># we don't actually do this:
combination[r-1] += 1
</code></pre>
<p>然而,这可能会过早打破条件2。因此,<em>如果</em>该操作将破坏条件2,我们将增加前面的元素并相应地调整最后一个元素。这有点像计算以10为基数的整数:“如果最后一个数字大于9,则增加前一个数字,并使最后一个数字为0。”但是,我们没有添加零,而是填充元组,以使条件1为真。在</p>
<pre><code># if above does not work
combination[r-2] += 1
combination[r-1] = combination[r-2] + 2
</code></pre>
<p>问题是,第二行可能会再次打破条件二。所以我们实际上要做的是,跟踪最后一个元素,这就是使用<code>a</code>所做的工作。我们还使用<code>p</code>变量来引用我们正在查看的index current元素。在</p>
<pre><code>p = r-1
a = 1
while p > 0 and combination[p] + a > n:
p -= 1
a += 2
</code></pre>
<p>我们从右到左(p=r-1,p-=1)遍历结果元组的项。
最初,我们希望在最后一个项(a=1)中添加一个,但在单步执行元组时,我们实际上希望将最后一个项替换为前一项的值加上<code>2*x</code>,其中{<cd13>}是两个项之间的距离。(a+=2,组合[p]+a)</p>
<p>我们从第2项的增量开始,找到了第2项的增量:</p>
<pre><code>combination[p:] = range(combination[p]+1, combination[p] + 2*(r-p), 2)
</code></pre>
<p>就这样。当我第一次想到它的时候,它看起来是那么简单,但是整个函数中的所有算法都是一个很好的地方,因为只有一个错误,而且描述它比它应该是困难的。当我添加内部循环时,我应该知道我有麻烦了:)</p></li>
</ul>
<h2>性能方面</h2>
<p>不幸的是,用Python编写充满算术的循环并不是最有效的方法。其他解决方案接受这种现实,并使用列表理解或过滤将繁重的工作推到Python运行时中。在我看来这是正确的做法。在</p>
<p>另一方面,我很确定如果这是C,我的解决方案会比大多数解决方案的性能好得多。内部while循环是O(logr),它会在适当的位置和相同的O(logr)中改变结果。除了结果和两个变量外,它不消耗额外的堆栈帧,也不消耗任何内存。但显然这不是C,所以不是这真的很重要。在</p>