如何生成多个整数列表间的所有元素组合（笛卡尔积）？

需求说明 #

输入四个整数列表：

{1, 2, 3}
{2, 4}
{3, 4}
{5, 6}

需要生成所有从每个列表中各取一个元素组成的组合，预期输出示例：

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

Python 实现 #

Python 可以直接用标准库 itertools 的 product 方法，它专门生成多个可迭代对象的笛卡尔积，完美匹配需求：

import itertools

# 定义输入列表集合
input_lists = [[1, 2, 3], [2, 4], [3, 4], [5, 6]]
# 生成所有组合（返回元组迭代器）
combination_tuples = itertools.product(*input_lists)
# 转换为列表的列表格式
result = [list(item) for item in combination_tuples]
print(result)

运行代码即可得到预期格式，itertools.product(*input_lists) 会自动遍历每个列表的元素，生成所有跨列表组合。

JavaScript 实现 #

JavaScript 可以用递归方式实现，支持任意数量的输入列表：

function generateAllCombinations(lists) {
    // 递归终止：只剩一个列表时，把每个元素单独包装成数组
    if (lists.length === 1) {
        return lists[0].map(num => [num]);
    }
    // 拆分第一个列表和剩余列表
    const firstList = lists[0];
    const restCombinations = generateAllCombinations(lists.slice(1));
    // 组合第一个列表元素与剩余列表的所有组合
    const finalResult = [];
    firstList.forEach(item => {
        restCombinations.forEach(comb => {
            finalResult.push([item, ...comb]);
        });
    });
    return finalResult;
}

// 定义输入列表
const inputLists = [[1, 2, 3], [2, 4], [3, 4], [5, 6]];
const combinations = generateAllCombinations(inputLists);
console.log(combinations);

递归思路是拆解问题：先得到后面所有列表的组合，再把第一个列表的每个元素和这些组合一一拼接，最终得到全量组合。

Java 实现 #

Java 可以用回溯法实现，通过递归遍历每个列表元素，收集所有可能的组合：

import java.util.ArrayList;
import java.util.List;

public class CombinationGenerator {
    public static List<List<Integer>> generateCombinations(List<List<Integer>> inputLists) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, inputLists, new ArrayList<>(), 0);
        return result;
    }

    private static void backtrack(List<List<Integer>> result, List<List<Integer>> inputLists, List<Integer> currentComb, int listIndex) {
        // 遍历完所有列表，保存当前组合
        if (listIndex == inputLists.size()) {
            result.add(new ArrayList<>(currentComb));
            return;
        }
        // 遍历当前列表元素，加入组合后递归处理下一个列表
        for (int num : inputLists.get(listIndex)) {
            currentComb.add(num);
            backtrack(result, inputLists, currentComb, listIndex + 1);
            // 回溯，移除当前元素尝试下一个可能
            currentComb.remove(currentComb.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> inputLists = new ArrayList<>();
        inputLists.add(List.of(1, 2, 3));
        inputLists.add(List.of(2, 4));
        inputLists.add(List.of(3, 4));
        inputLists.add(List.of(5, 6));
        List<List<Integer>> combinations = generateCombinations(inputLists);
        System.out.println(combinations);
    }
}

回溯法核心是“尝试-回退”：每次将当前列表的一个元素加入临时组合，处理完下一个列表后移除该元素，继续尝试当前列表的下一个元素，直到遍历完所有可能。

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