如何用Python生成列表的所有分组(最好是迭代工具)

Question

如果我有一个序列，例如1，2，3，4，如何使用迭代工具从它生成以下组：

(1) (2) (3) (4)

(1 ) (3) (4)

(1) (2 )( 3) (4)

(1) (2) (3 )

(1 2) (3 4)

(1 2 3) (4)

(1) (2 3 4)

(1 2 3 4)

我分组的顺序不是用分离器:最初我用三个分离器把它们分成四组，然后用两个分离器把它们分成三组(两种方法分成三组)等等。

如果迭代工具是不可能的，我还能如何生成它呢？

Answer 1

对于列表中的n项，列表项之间存在n-1位置，其中可能存在分离，也可能没有分离。因此，我们可以让每个分组对应于一个n-1位列表，其中0表示分离，1表示不分离。

def generate_groupings(xs):
    for bits in range(2 ** (len(xs)-1)):  # int representing n-1 bits
        grouping = [(xs[0],)]             # grouping starts with first item
        for x in xs[1:]:                  # for each remaining item...
            bits, b = divmod(bits, 2)     # pop one bit off of the list
            if b:                         # case 1: no separation
                grouping = grouping[:-1] + [grouping[-1] + (x,)]
            else:                         # case 0: separation
                grouping += [(x,)]
        yield grouping        

list(generate_groupings([1,2,3]))
# [[(1,), (2,), (3,)], [(1, 2), (3,)], [(1,), (2, 3)], [(1, 2, 3)]]

回答你的后续问题

如何从上面的表单列表中获得一个值：(1+2+3)*1 + (1+2)*2 + (3)*1 + (1)*1 + (2+3)*2 +(1+2+3)*3，即组*长度中元素的和

sum(sum(g)*len(g) for gs in generate_groupings([1,2,3]) for g in gs)
# 44