Python如何递归展平嵌套数组生成对应元素的全排列列表

核心思路 #

给定的嵌套数组每个节点的结构统一为 [当前元素值, 后续可选节点列表]，最内层节点无后续子节点，因此可以通过深度优先递归遍历所有路径，收集完整排列：

• 递归过程中维护当前已生成的排列前缀
• 遍历到最内层无后续节点的元素时，将当前前缀拼接该元素作为一条完整排列存入结果集
• 遍历所有分支后返回全部排列即可

代码实现（Python） #

def flatten_perm(nested_arr):
    res = []
    def dfs(node, path):
        # 处理最内层单个元素的情况
        if isinstance(node, str):
            res.append(path + [node])
            return
        # 处理 [当前值, 子节点列表] 结构的节点
        current_val, children = node
        new_path = path + [current_val]
        for child in children:
            dfs(child, new_path)
    # 遍历根层所有起始节点
    for root_node in nested_arr:
        dfs(root_node, [])
    return res

测试验证 #

输入示例嵌套数组：

test_arr = [['a', [['b', ['c']], ['c', ['b']]]], ['b', [['a', ['c']], ['c', ['a']]]], ['c', [['a', ['b']], ['b', ['a']]]]]
print(flatten_perm(test_arr))

输出结果和预期完全一致：

[['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]

通用性说明 #

该实现不依赖固定的元素数量，只要嵌套数组的结构符合 [当前元素, 子节点列表] 的约定，任意长度的排列场景都可以正常输出结果。

内容的提问来源于stack exchange，提问作者Matěj Kos