如何用Python递归实现字典中各列表元素的全组合生成

问题说明 #

给定一个包含任意数量键值对的字典，每个键对应一个元素列表，需要从每个列表中各取一个元素，生成所有可能的组合列表。

示例输入 #

{'key1': [1, 2], 'key2': [3, 4, 5], 'key3': [6, 7]}

期望输出 #

[[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[2,3,6],[2,3,7],[2,4,6],[2,4,7],[2,5,6],[2,5,7]]

递归实现方案 #

递归的核心思路是拆解问题：每次处理字典中的一个列表，将该列表的每个元素与剩余列表生成的所有组合进行拼接，逐步缩小问题规模直到终止条件触发。

基础递归代码 #

def generate_combinations(dictionary):
    # 提取字典的所有值列表（Python 3.7+ 字典保留插入顺序，保证组合顺序和键顺序一致）
    value_lists = list(dictionary.values())
    # 递归终止条件：没有剩余列表时，返回包含空列表的列表作为拼接基础
    if not value_lists:
        return [[]]
    
    # 拆分出第一个列表和剩余的列表集合
    first_list = value_lists[0]
    # 生成剩余键值对组成的新字典，递归获取其组合
    rest_dict = dict(zip(list(dictionary.keys())[1:], value_lists[1:]))
    rest_combinations = generate_combinations(rest_dict)
    
    # 拼接当前元素与剩余组合，生成最终结果
    result = []
    for item in first_list:
        for combo in rest_combinations:
            result.append([item] + combo)
    return result

# 测试示例
input_dict = {'key1': [1, 2], 'key2': [3, 4, 5], 'key3': [6, 7]}
print(generate_combinations(input_dict))

简洁版递归代码（列表推导式） #

可以用列表推导式简化代码逻辑，效果完全一致：

def generate_combinations(dictionary):
    value_lists = list(dictionary.values())
    if not value_lists:
        return [[]]
    first_list, rest_lists = value_lists[0], value_lists[1:]
    rest_dict = dict(zip(list(dictionary.keys())[1:], rest_lists))
    return [[item] + combo for item in first_list for combo in generate_combinations(rest_dict)]

非递归补充方案（可选） #

如果不需要严格用递归实现，Python标准库的itertools.product可以直接生成笛卡尔积，转换为列表即可得到结果：

import itertools

input_dict = {'key1': [1, 2], 'key2': [3, 4, 5], 'key3': [6, 7]}
combinations = list(map(list, itertools.product(*input_dict.values())))
print(combinations)

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