<h2>概述</h2>
<p>关键是遍历累积组合,直到达到索引为止。在</p>
<h2>解决方案</h2>
<pre><code>from math import factorial
def comb(n, r):
'Combinations of n things taken r at a time'
return factorial(n) // (factorial(r) * factorial(n - r))
def nth_combination(population, r, index):
'Equivalent to list(combinations(population, r))[index]'
n = len(population)
c = comb(n, r)
if index < 0:
index += c
if index < 0 or index >= c:
raise IndexError
if r < 0 or r > n:
raise ValueError
result = []
while r:
c, n, r = c*r//n, n-1, r-1
while index >= c:
index -= c
c, n = c*(n-r)//n, n-1
result.append(population[-1-n])
return tuple(result)
</code></pre>
<h2>优化</h2>
<p>如果需要考虑速度,则可以构建更快版本的<em>comb()</em>函数。在</p>
<p>一种方法是预先计算阶乘,然后在需要时进行查找:</p>
^{pr2}$
<p>还有另一种方法可以完全避免大阶乘,而且不需要辅助存储:</p>
<pre><code>def comb(n, r):
c = 1
r = min(r, n-r)
for i in range(1, r+1):
c = c * (n - r + i) // i
return c
</code></pre>
<h2>工作原理</h2>
<p>首先将组合分解为其组成组:</p>
<pre><code>def groups(n, r):
return [comb(n-i-1, r-1) for i in range(n-r+1)]
>>> comb(8, 3)
56
>>> groups(8, 3)
[21, 15, 10, 6, 3, 1]
</code></pre>
<p>这意味着,当您一次运行<code>itertools.combinations('ABCDEFGH', 3)</code>处理<code>n=8</code>个字母时,有56个组合。前21个以<code>A</code>开头,后15个以<code>B</code>开头,下10个以<code>C</code>开头,下6个以<code>D</code>开头,下3个以<code>E</code>开头,最后1个以<code>F</code>开头。在</p>
<p>假设你想找到56个组合中的第25个。它属于第二组,所以你的第一个字母是<code>B</code>。在</p>
<p>由于25-21是4,那么您需要在<code>itertools.combinations('CDEFGH', 2)</code>定义的“B”组的15个成员中找到第4个组合。重复上述过程,直到所有的字母都被提取出来。在</p>
<h2>测试</h2>
<p>下面是一个测试,以确保它能产生预期的结果:</p>
<pre><code>from itertools import combinations
population = 'ABCDEFGH'
for r in range(len(population) + 1):
for i, expected in enumerate(combinations(population, r)):
actual = locate(list(population), r, i)
assert expected == actual
</code></pre>