python - 当组的长度已知时，从列表中形成 2、3、4 组的所有可能组合

Question

假设我有像(1,2,3,4,5).

我想将它分组1,1,0为（1 组 2）、（1 组 3）和（0 组 4）。

结果将是(1,2), (3,4,5), (2,3), (1,4,5), (3,4), (1,2,5),(4,5), (1,2,3) (1,3), (2,4,5)等等

我该如何实施？这是可能的itertools吗？

标签： python

Answer 1

您可以使用组合，但您仍然必须为组分区实现自己的逻辑：

from itertools import combinations

def group(T,g234):
    if sum(g234) == 0: yield [];return                 # end resursion
    size = next(g for g,n in enumerate(g234,2) if n>0) # first count>0
    g234 = list(g234)                                  # remaining groups
    g234[size-2] -= 1
    for combo in combinations(range(len(T)),size):     # combine tuple indexes
        part   = tuple(T[i] for i in combo)            # subgroup of combination
        others = [v for i,v in enumerate(T) if i not in combo]  # remaining
        yield from ([part]+rest for rest in group(others,g234)) # assemble parts

输出：

print(*group((1,2,3,4,5),[1,1,0]),sep="\n")
[(1, 2), (3, 4, 5)]
[(1, 3), (2, 4, 5)]
[(1, 4), (2, 3, 5)]
[(1, 5), (2, 3, 4)]
[(2, 3), (1, 4, 5)]
[(2, 4), (1, 3, 5)]
[(2, 5), (1, 3, 4)]
[(3, 4), (1, 2, 5)]
[(3, 5), (1, 2, 4)]
[(4, 5), (1, 2, 3)]

print(*group((1,2,3,4,5,6),(0,2,0)),sep="\n")
[(1, 2, 3), (4, 5, 6)]
[(1, 2, 4), (3, 5, 6)]
[(1, 2, 5), (3, 4, 6)]
[(1, 2, 6), (3, 4, 5)]
[(1, 3, 4), (2, 5, 6)]
[(1, 3, 5), (2, 4, 6)]
...

print(*group((1,2,3,4,5,6),(3,0,0)),sep="\n")
[(1, 2), (3, 4), (5, 6)]
[(1, 2), (3, 5), (4, 6)]
[(1, 2), (3, 6), (4, 5)]
[(1, 2), (4, 5), (3, 6)]
[(1, 2), (4, 6), (3, 5)]
[(1, 2), (5, 6), (3, 4)]
...

print(*group((1,2,3,4,5,6,7,8,9),(1,1,1)),sep="\n")
[(1, 2), (3, 4, 5), (6, 7, 8, 9)]
[(1, 2), (3, 4, 6), (5, 7, 8, 9)]
[(1, 2), (3, 4, 7), (5, 6, 8, 9)]
[(1, 2), (3, 4, 8), (5, 6, 7, 9)] 
...

[编辑]迭代版本。使用 deque 作为递归调用堆栈的替代品：

from itertools import combinations
from collections import deque
def group(T,g234):
    stack = deque([(T,g234,[],None)]) #tuple, groups, parts, combo_iterator
    while stack:
        T,g234,parts,cIter = stack.pop()
        #print(len(T),g234,len(parts),bool(cIter))
        if cIter is None:
            if not sum(g234): yield parts;continue  # partition complete
            size = next(g for g,n in enumerate(g234,2) if n>0) # first count>0
            g234 = list(g234)                                  # remaining groups
            g234[size-2] -= 1
            cIter = combinations(range(len(T)),size)     # combine tuple indexes
        combo = next(cIter,None)
        if combo is None: continue
        stack.append((T,g234,parts,cIter))
        part   = tuple(T[i] for i in combo)            # subgroup of combination
        others = [v for i,v in enumerate(T) if i not in combo]  # remaining
        stack.append((others,g234,parts+[part],None))           # assemble parts

输出：

for parts in group(range(1000),(500, 0,0)):
    print(parts[:3],"...",parts[-3:])

[(0, 1), (2, 3), (4, 5)] ... [(994, 995), (996, 997), (998, 999)]
[(0, 1), (2, 3), (4, 5)] ... [(994, 995), (996, 998), (997, 999)]
[(0, 1), (2, 3), (4, 5)] ... [(994, 995), (996, 999), (997, 998)]
[(0, 1), (2, 3), (4, 5)] ... [(994, 995), (997, 998), (996, 999)]
[(0, 1), (2, 3), (4, 5)] ... [(994, 995), (997, 999), (996, 998)]
[(0, 1), (2, 3), (4, 5)] ... [(994, 995), (998, 999), (996, 997)]
...