如何按特定规则展平嵌套列表并生成所有排列路径？

问题分析 #

你需要处理混合普通元素（如唯一元组）和子列表的输入列表，生成所有可能的「路径」：每个子列表中选择一个元素，普通元素直接保留，最终组合数等于所有子列表长度的乘积。比如输入[(0, 0), (1, 0), [(1, 1), (2, 1)], [(3, 0), (3, 1), (3, 2)]]时，预期输出6个组合（2×3），但现有代码仅返回3个，原因是代码只处理了单个子列表的选择，没有处理多子列表的笛卡尔积组合。

解决方案 #

方法1：使用itertools.product（简洁高效） #

核心思路是先将原列表转换为「可选值集合列表」，再计算这些集合的笛卡尔积，每个积对应一条路径：

• 普通元素（非列表）：可选值只有自身，包装为单元素列表
• 子列表：可选值就是子列表本身

代码实现：

import itertools

def generate_all_paths(input_list):
    # 构建每个位置的可选值集合
    choices = []
    for item in input_list:
        if isinstance(item, list):
            choices.append(item)
        else:
            choices.append([item])
    # 计算笛卡尔积，每个元组对应一条路径，转换为列表
    return [list(path) for path in itertools.product(*choices)]

# 测试案例1
test1 = [(0, 0), (1, 0), [(1, 1), (2, 1)], (3, 0)]
print(generate_all_paths(test1))
# 输出：[[(0, 0), (1, 0), (1, 1), (3, 0)], [(0, 0), (1, 0), (2, 1), (3, 0)]]

# 测试案例2
test2 = [(0, 0), (1, 0), [(1, 1), (2, 1)], [(3, 0), (3, 1), (3, 2)]]
print(generate_all_paths(test2))
# 输出6个组合，符合预期

方法2：递归实现（满足你的递归思路） #

如果不想依赖itertools，可以用递归遍历每个元素，逐步构建路径：

def generate_all_paths_recursive(input_list):
    # 递归终止条件：空列表返回空路径
    if not input_list:
        return [[]]
    first_item = input_list[0]
    rest_paths = generate_all_paths_recursive(input_list[1:])
    # 如果第一个元素是列表，遍历每个元素和剩余路径组合
    if isinstance(first_item, list):
        result = []
        for elem in first_item:
            result.extend([[elem] + path for path in rest_paths])
        return result
    # 普通元素，直接和剩余路径组合
    else:
        return [[first_item] + path for path in rest_paths]

# 测试效果和方法1一致
print(generate_all_paths_recursive(test2))

现有代码的问题分析 #

你的代码逻辑存在两个关键缺陷：

1. 仅遍历了第一个子列表的索引，然后用同一个索引j去获取所有子列表的元素，这会导致多子列表时，所有子列表都选同一个位置的元素，无法生成交叉组合。
2. 依赖未初始化的全局变量path_list，逻辑上没有处理多子列表的独立选择需求。

上述两种方法都能正确处理任意数量的子列表，生成所有符合要求的路径组合。

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