从有序列表递归地生成组合

Question

给定一个'n'元素的有序列表，我想对列表进行切片，只生成一次子列表的每个不同排列，同时保持原始列表的顺序-即生成输入列表的每个Composition。(这与从我的输入列表中计算所有可能的子列表的可能组合不同)。

例如，给定输入列表[A,B,C,D]，我的输出将是以下8个嵌套列表:

[[A,B,C,D]], [[A,B,C],[D]], [[A,B],[C,D]], [[A,B],[C],[D]], [[A],[B,C],[D]], [[A],[B],[C,D]], [A,[B,C,D]], [[A],[B],[C],[D]].

绘制可能排列的树表明这个问题将适合递归算法，但我不确定如何在Python中实现它以获得最大的速度和效率，并将非常感谢您的建议和指导。

Answer 1

def composition(seq):
    seq = tuple(seq)
    for i in range(2**(len(seq)-1)):
        result = [[seq[0]]]
        for j in range(len(seq)-1):
            if i & (1<<j):
                result.append([seq[j+1]])
            else:
                result[-1].append(seq[j+1])
        yield result
if __name__=="__main__":
    from pprint import pprint
    pprint(list(composition('ABCD')))

参考:https://en.wikipedia.org/wiki/Composition_(组合)