python - 从有序列表递归生成组合

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_(combinatorics)