<p>如评论中所述,OP似乎正在寻找<a href="https://jwood000.github.io/RcppAlgos/articles/GeneralCombinatorics.html#partitions-of-groups-of-equal-size-with-combogroups" rel="nofollow noreferrer">Partitions of Groups of Equal Size</a></p>
<p>下面的代码是从<code>C++</code>中实现的算法转换而来的,在这里可以找到:<a href="https://github.com/jwood000/RcppAlgos/blob/master/src/ComboGroupsUtils.cpp" rel="nofollow noreferrer">https://github.com/jwood000/RcppAlgos/blob/master/src/ComboGroupsUtils.cpp</a><strong><sup>*</sup></strong>。我将注释放在下面自己的一个块中,然后是pythonized代码(注意,这是一个直接翻译,可能还有改进的余地)</p>
<blockquote>
<p>******* Overview of the Crucial Part of the Algorithm *******</p>
<hr/>
<p><code>last1</code> is one plus the upper bound in the previous section, so to obtain the current current upper bound, we must first add the size of a section (i.e. <code>grpSize</code>) and subtract one. We can now compute the length we need to reset <code>v</code> by subtracting <code>idx1</code>. E.g.</p>
<p>Given a portion of <code>v</code> with <code>grpSize = 4</code>, <code>idx1 = 9</code>, 6 groups (24 subjects) and base 0:</p>
<pre><code> prev sections bound (index = 8)
/ \ |
............. 8 | 9 12 23 24 | 10 20 21 22 | 11 ...
|
idx1 (equal to last1, in this case)
</code></pre>
<p>Sort <code>v</code> past <code>idx1</code>:</p>
<pre><code> ... 8 | 9 12 10 11 | 13 14 15 16 | 17...
</code></pre>
<p>Determine the index, <code>idx3</code>, such that <code>v[idx3]</code> > <code>v[idx1]</code></p>
<pre><code> ... 8 | 9 12 10 11 | 13 14 15 16 | 17 ...
| |
idx1 idx3
</code></pre>
<p>Swap <code>idx1</code> and <code>idx3</code>:</p>
<pre><code> ... 8 | 9 13 10 11 | 12 14 15 16 | 17...
</code></pre>
<p>Move enough indices after <code>idx1</code> to fill that specific group:</p>
<pre><code> ... 8 | 9 13 __ __ | 10 11 12 14 | 15 16 ...
</code></pre>
<p>Identify and move indices that are successively incrementing values of <code>v</code> past <code>idx1</code>:</p>
<pre><code> ... 8 | 9 13 14 15 | 10 11 12 16 | 17 ...
</code></pre>
<p>The last two steps are accomplished with <code>std::rotate</code>. This completes the algorithm.</p>
</blockquote>
<p>以下是一些帮助功能:</p>
<pre><code>def rotate(l, n):
return l[n:] + l[:n]
def numGroupCombs(n, nGrps, grpSize):
result = 1
for i in range(n, nGrps, -1):
result *= i
result = int(result)
myDiv = 1
for i in range(2, grpSize + 1):
myDiv *= i
result /= myDiv**nGrps
return int(result)
</code></pre>
<p>这是主生成器(旋转函数是从这个答案<a href="https://stackoverflow.com/a/9457864/4408538">Python list rotation</a>得到的):</p>
<pre><code>def ComboGroups(v, nGrps, grpSize):
if not isinstance(v, list):
z = list(v)
else:
z = v.copy()
for i in range(numGroupCombs(len(z), nGrps, grpSize)):
yield z.copy()
idx1 = (nGrps - 1) * grpSize - 1
idx2 = len(z) - 1;
last1 = (nGrps - 2) * grpSize + 1
while (idx2 > idx1 and z[idx2] > z[idx1]):
idx2 -= 1
if (idx2 + 1) < len(z):
if z[idx2 + 1] > z[idx1]:
z[idx1], z[idx2 + 1] = z[idx2 + 1], z[idx1]
else:
while idx1 > 0:
tipPnt = z[idx2]
while (idx1 > last1 and tipPnt < z[idx1]):
idx1 -= 1
if tipPnt > z[idx1]:
idx3 = idx1 + 1
z[idx3:] = sorted(z[idx3:])
xtr = last1 + grpSize - idx3
while z[idx3] < z[idx1]:
idx3 += 1
z[idx3], z[idx1] = z[idx1], z[idx3]
z[(idx1 + 1):(idx3 + xtr)] = rotate(z[(idx1 + 1):(idx3 + xtr)], idx3 - idx1)
break
else:
idx1 -= 2
idx2 -= grpSize
last1 -= grpSize
</code></pre>
<p>下面是一个示例用法(<a href="https://ideone.com/kygF03" rel="nofollow noreferrer">https://ideone.com/kygF03</a>):</p>
<pre><code>import time
def example(z, nGrps, verbose = True):
grpSize = int(len(z) / nGrps)
if verbose:
for a in ComboGroups(z, nGrps, grpSize):
print([a[i:i + grpSize] for i in range(0, len(a), grpSize)])
else:
start = time.time()
for a in ComboGroups(z, nGrps, grpSize):
b = a
end = time.time()
print(end - start)
example(list(range(1, 9)), 2)
[[1, 2, 3, 4], [5, 6, 7, 8]]
[[1, 2, 3, 5], [4, 6, 7, 8]]
[[1, 2, 3, 6], [4, 5, 7, 8]]
[[1, 2, 3, 7], [4, 5, 6, 8]]
[[1, 2, 3, 8], [4, 5, 6, 7]]
[[1, 2, 4, 5], [3, 6, 7, 8]]
[[1, 2, 4, 6], [3, 5, 7, 8]]
[[1, 2, 4, 7], [3, 5, 6, 8]]
[[1, 2, 4, 8], [3, 5, 6, 7]]
[[1, 2, 5, 6], [3, 4, 7, 8]]
[[1, 2, 5, 7], [3, 4, 6, 8]]
[[1, 2, 5, 8], [3, 4, 6, 7]]
[[1, 2, 6, 7], [3, 4, 5, 8]]
[[1, 2, 6, 8], [3, 4, 5, 7]]
[[1, 2, 7, 8], [3, 4, 5, 6]]
[[1, 3, 4, 5], [2, 6, 7, 8]]
[[1, 3, 4, 6], [2, 5, 7, 8]]
[[1, 3, 4, 7], [2, 5, 6, 8]]
[[1, 3, 4, 8], [2, 5, 6, 7]]
[[1, 3, 5, 6], [2, 4, 7, 8]]
[[1, 3, 5, 7], [2, 4, 6, 8]]
[[1, 3, 5, 8], [2, 4, 6, 7]]
[[1, 3, 6, 7], [2, 4, 5, 8]]
[[1, 3, 6, 8], [2, 4, 5, 7]]
[[1, 3, 7, 8], [2, 4, 5, 6]]
[[1, 4, 5, 6], [2, 3, 7, 8]]
[[1, 4, 5, 7], [2, 3, 6, 8]]
[[1, 4, 5, 8], [2, 3, 6, 7]]
[[1, 4, 6, 7], [2, 3, 5, 8]]
[[1, 4, 6, 8], [2, 3, 5, 7]]
[[1, 4, 7, 8], [2, 3, 5, 6]]
[[1, 5, 6, 7], [2, 3, 4, 8]]
[[1, 5, 6, 8], [2, 3, 4, 7]]
[[1, 5, 7, 8], [2, 3, 4, 6]]
[[1, 6, 7, 8], [2, 3, 4, 5]]
</code></pre>
<p>对于您的示例,上面未优化的实现可以在4秒钟内迭代所有<code>2,858,856</code>结果</p>
<pre><code>example(list(range(1, 19)), 3, False)
4.4308202266693115
</code></pre>
<p>作为参考,相同的算法在<code>C++</code>中运行大约0.12秒</p>
<p><strong><sup>*</sup></strong>我是<code>RcppAlgos</code>的作者</p>