如何生成特定集合元素的有序组合列表？求递归解决方案

嘿，我完全懂你的痛点！迭代法确实在集合数量固定的时候好用，但面对可变数量的子列表时，递归才是更优雅灵活的解决方案——它能自动适配任意多的输入集合，核心就是把问题层层拆解，直到触达简单的基线条件。

递归思路拆解 #

递归的关键在于把复杂问题拆成简单子问题：

• 基线条件：
  • 如果输入的集合列表是空的，返回[[]]（空集合的笛卡尔积就是包含空列表的集合，这是递归的终止锚点）；
  • 如果只剩一个子列表，直接返回该列表中每个元素单独组成的列表（比如输入[[1,2]]，返回[[1], [2]]）。
• 递归步骤：
  1. 取出第一个子列表；
  2. 递归计算剩下所有子列表的笛卡尔积；
  3. 把第一个子列表的每个元素，分别拼接到递归结果的每个组合开头，收集所有这些新组合。

Python代码实现 #

先写一个清晰易懂的版本，方便理解每一步：

def cartesian_product(sets):
    # 基线：没有更多集合，返回包含空列表的列表
    if not sets:
        return [[]]
    
    # 拆分第一个集合和剩余集合
    first_set, remaining_sets = sets[0], sets[1:]
    
    # 递归计算剩余集合的笛卡尔积
    rest_combinations = cartesian_product(remaining_sets)
    
    # 拼接第一个集合的元素和剩余组合
    result = []
    for item in first_set:
        for combo in rest_combinations:
            result.append([item] + combo)
    
    return result

测试你给出的例子：

input_sets = [['a', 'b'], ['X', 'Y', 'Z'], [1, 2]]
print(cartesian_product(input_sets))

输出完全符合你的预期，而且哪怕你传入6个子列表，这个函数也能完美处理，因为递归会自动逐层拆解。

如果追求代码简洁，还可以用列表推导式简化成一行核心逻辑：

def cartesian_product(sets):
    if not sets:
        return [[]]
    first, rest = sets[0], sets[1:]
    return [[item] + combo for item in first for combo in cartesian_product(rest)]

工作原理快速说明 #

拿你的例子走一遍流程：

1. 第一次调用处理[['a','b'], ['X','Y','Z'], [1,2]]，取出['a','b']，递归处理[['X','Y','Z'], [1,2]]；
2. 第二次调用取出['X','Y','Z']，递归处理[[1,2]]；
3. 第三次调用只剩一个集合，返回[[1], [2]]；
4. 第二次调用把X/Y/Z分别拼接到[[1], [2]]的每个组合前，得到[[X,1], [X,2], [Y,1], [Y,2], [Z,1], [Z,2]]；
5. 第一次调用把a/b分别拼接到上述结果的每个组合前，就得到了你要的最终列表。

这种递归方式完全不限制子列表的数量，不管是3个还是6个，逻辑都是通用的～

内容的提问来源于stack exchange，提问作者Michał Bartoś