如何获得将长度为n的列表划分为m个子列表的所有可能组合

Question

在我的具体情况下，我想获得将长度为 20 的列表划分为 4 个子列表的所有可能组合。子列表的长度可以从 1 到 17。因此，我想要一个包含所有可能组合的子列表列表。

开头列表：

list_init = [a, b,  c,  d,  e,  f,  g,  h,  i,  j,  k,  l,  m,  n,  o,  p,  q,  r,  s,  t]

包含所有组合的列表列表列表：

list_combs = [
[[a],   [b],    [c],    [d, e,  f,  g,  h,  i,  j,  k,  l,  m,  n,  o,  p,  q,  r,  s,  t]],
[[a,d], [b],    [c],    [e, f,  g,  h,  i,  j,  k,  l,  m,  n,  o,  p,  q,  r,  s,  t]],
[[a,d,e],   [b],    [c],    [f, g,  h,  i,  j,  k,  l,  m,  n,  o,  p,  q,  r,  s,  t]],
.
.
.
]

Answer 1

您可以通过将长度为 1、2、3...

from itertools import combinations
def partCombo(L,N=4):
    if N==1: yield [L]; return
    for size in range(1,len(L)-N+2):
        for combo in combinations(range(len(L)),size): # index combinations
            part      = list(L[i] for i in combo)      # first part
            remaining = list(L)
            for i in reversed(combo): del remaining[i] # unused items
            yield from ([part]+rest for rest in partCombo(remaining,N-1))

输出：

aList = list("abcdefg")
for part in partCombo(aList):
    print(part)

[['a'], ['b'], ['c'], ['d', 'e', 'f', 'g']]
[['a'], ['b'], ['d'], ['c', 'e', 'f', 'g']]
[['a'], ['b'], ['e'], ['c', 'd', 'f', 'g']]
[['a'], ['b'], ['f'], ['c', 'd', 'e', 'g']]
[['a'], ['b'], ['g'], ['c', 'd', 'e', 'f']]
[['a'], ['b'], ['c', 'd'], ['e', 'f', 'g']]
[['a'], ['b'], ['c', 'e'], ['d', 'f', 'g']]
[['a'], ['b'], ['c', 'f'], ['d', 'e', 'g']]
[['a'], ['b'], ['c', 'g'], ['d', 'e', 'f']]
[['a'], ['b'], ['d', 'e'], ['c', 'f', 'g']]
[['a'], ['b'], ['d', 'f'], ['c', 'e', 'g']]
[['a'], ['b'], ['d', 'g'], ['c', 'e', 'f']]
[['a'], ['b'], ['e', 'f'], ['c', 'd', 'g']]
[['a'], ['b'], ['e', 'g'], ['c', 'd', 'f']]
[['a'], ['b'], ['f', 'g'], ['c', 'd', 'e']]
[['a'], ['b'], ['c', 'd', 'e'], ['f', 'g']]
... and many more ... (total 8400)

对于包含 20 个项目的列表，将有 1,085,570,781,624 种组合。

from math import factorial
def countCombos(L,N=4):
    if N==1: return 1
    result = 0
    for size in range(1,L-N+2):
        c = factorial(L)//factorial(size)//factorial(L-size)
        c *= countCombos(L-size,N-1)
        result += c
    return result

sum(1 for _ in partCombo("abcdefg"))    # 8400
sum(1 for _ in partCombo("abcdefghij")) # 818520

countCombos(7)  # 8400 
countCombos(10) # 818520
countCombos(15) # 1016542800
countCombos(20) # 1085570781624

有那么多组合（20 项），将不可能输出所有组合的列表（它永远不会适合内存）。这就是函数被写成生成器的原因。尽管如此，在包含 20 个项目的列表中遍历生成器函数生成的所有组合仍需要很长时间（数周）。

如何获得将长度为n的列表划分为m个子列表的所有可能组合

How to get all possible combinations of dividing a list of length n into m sublists

python

list

combinatorics