如何生成嵌套列表各层级子列表元素的全排列？

这个问题我之前碰到过，靠随机生成再去重真的太不高效了，其实我们可以用递归结合全排列+笛卡尔积的方式精准生成所有符合要求的结果，根本不用碰去重的麻烦事！

为什么随机生成去重不是好方案？ #

先给你算一笔账：拿你举的例子[['a', 'b', 'c'], ['d'], ['e', 'f', ['g', ['h', 'i']]]]来说，所有符合要求的排列总数是：

• 第一层子列表：3! = 6种
• 第二个子列表：1! = 1种
• 第三个子列表：2! * (1! * 2!) = 2*2=4种
• 总排列数：614=24种

如果靠循环10000次随机生成再去重，不仅要做9976次无用功，还要处理列表不可哈希的去重问题（得转成元组再去重，再转回列表），而且万一随机数不够"随机"，还可能漏掉某些排列，完全是舍近求远。

最优方案：递归+全排列+笛卡尔积 #

我们可以用递归遍历每个层级，对每个子列表生成内部元素的全排列，再用笛卡尔积组合所有可能的情况——这样能精准生成所有符合要求的排列，没有重复，效率拉满。

代码实现 #

先导入需要的工具模块：

import itertools

然后写递归函数：

def generate_all_permutations(nested_list):
    # 基础情况：如果不是列表，单个元素没有排列可能，返回包含它的列表
    if not isinstance(nested_list, list):
        return [nested_list]
    
    # 第一步：递归处理每个子元素，得到每个子元素的所有可能排列结果
    element_permutations = []
    for elem in nested_list:
        element_permutations.append(generate_all_permutations(elem))
    
    # 第二步：生成当前层级列表的元素顺序全排列（即当前列表的索引排列）
    all_index_permutations = itertools.permutations(range(len(nested_list)))
    
    total_results = []
    # 遍历每个当前层级的元素顺序排列
    for idx_perm in all_index_permutations:
        # 取出当前顺序下，每个位置对应的子元素的所有排列选项
        current_options = [element_permutations[idx] for idx in idx_perm]
        # 用笛卡尔积把所有子元素的排列组合起来，得到当前顺序下的所有可能结果
        for combo in itertools.product(*current_options):
            total_results.append(list(combo))
    
    return total_results

测试代码 #

用你给的例子测试一下：

x = [['a', 'b', 'c'], ['d'], ['e', 'f', ['g', ['h', 'i']]]]
all_perms = generate_all_permutations(x)

print(f"总共有 {len(all_perms)} 种排列")
# 打印几个示例结果
for perm in all_perms[:3]:
    print(perm)

运行后会输出24种排列，比如：

[['c', 'b', 'a'], ['d'], ['f', 'e', ['g', ['i', 'h']]]]
[['c', 'a', 'b'], ['d'], ['f', 'e', ['g', ['h', 'i']]]]
[['b', 'c', 'a'], ['d'], ['f', 'e', ['g', ['i', 'h']]]]

代码逻辑解释 #

1. 递归遍历层级：从最外层到最内层，每个元素如果是列表就继续递归处理，如果是单个元素就返回它自己（作为基础排列）。
2. 当前层级的元素顺序排列：用itertools.permutations生成当前列表的所有索引排列，也就是当前列表元素的所有可能顺序。
3. 笛卡尔积组合子元素排列：对于当前层级的每一种元素顺序，把每个位置对应的子元素的所有排列做笛卡尔积，这样就得到了当前层级下所有包含子层级排列的结果。

这种方法直接计算所有可能的组合，没有冗余，一次性生成所有符合要求的排列，完全不需要去重。

内容的提问来源于stack exchange，提问作者user9440895