如何生成n个数组的唯一组合？树/图路径算法咨询

你要解决的是多个数组的笛卡尔积问题——也就是从每个数组中各取一个元素，生成所有可能的唯一组合（对应你说的“路径”），这确实可以用树的遍历思路实现，下面给你几个实用的实现方案：

示例翻译 #

示例1 #

arr1 = [0, 6, 3, 10]
arr2 = [75, 10]
arr3 = [99, 50]
arr4 = [10]

生成的所有组合（路径）：

0 75 99 10
0 75 50 10
0 10 99 10
0 10 50 10

对应的树结构：

0
     75        10
  99   50    99   50
10     10  10     10

示例2 #

arr1 = [0, 6, 3, 10]
arr2 = [75, 10]
arr3 = [99, 50]
arr4 = [10, 30, 60, 50]

生成的部分组合（路径）：

0 75 99 10
0 75 99 30
0 75 99 60
0 75 99 50
0 75 50 10
0 75 50 30
0 75 50 60
0 75 50 50
0 10 99 10
...

对应的树结构：

0
     75        10
  99   50    99   50
10 30 60 50 10 30 60 50

可行实现方案 #

1. 递归法（深度优先遍历DFS） #

从第一个数组开始，遍历每个元素，递归拼接后续数组的所有组合，直到处理完所有数组：

def cartesian_product(arrays):
    # 基准情况：只剩一个数组，返回单元素列表的集合
    if len(arrays) == 1:
        return [[x] for x in arrays[0]]
    # 递归处理剩余数组
    rest_combinations = cartesian_product(arrays[1:])
    # 拼接当前数组元素与后续组合
    result = []
    for num in arrays[0]:
        for combo in rest_combinations:
            result.append([num] + combo)
    return result

# 测试示例1
arrays = [[0,6,3,10], [75,10], [99,50], [10]]
for combo in cartesian_product(arrays):
    print(' '.join(map(str, combo)))

2. 迭代法（广度优先遍历BFS） #

用列表逐步构建组合，初始为空列表，依次将现有组合与当前数组的每个元素拼接：

def cartesian_product_iterative(arrays):
    result = [[]]
    for arr in arrays:
        temp = []
        for existing_combo in result:
            for num in arr:
                temp.append(existing_combo + [num])
        result = temp
    return result

# 测试示例2
arrays = [[0,6,3,10], [75,10], [99,50], [10,30,60,50]]
for combo in cartesian_product_iterative(arrays):
    print(' '.join(map(str, combo)))

3. 内置工具简化实现（Python） #

Python的itertools.product直接封装了笛卡尔积逻辑，是最简洁的实现方式：

import itertools

arrays = [[0,6,3,10], [75,10], [99,50], [10]]
for combo in itertools.product(*arrays):
    print(' '.join(map(str, combo)))

注意事项 #

• 组合总数是所有数组长度的乘积，若数组数量多、元素多，要注意内存占用，必要时分批处理避免溢出。
• 若需要去重（不同路径出现完全相同的元素组合），可将组合转为元组存入集合，再转回列表。

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