从有序列表递归生成组合

Question

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

例如，给定输入列表 [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)

从有序列表递归生成组合

Recursively generate Compositions from an ordered list

python

algorithm

recursion

list

combinatorics