如何遍历列表的笛卡尔积？求通用实现及C++解决方案

你的索引映射思路本质是将组合转换为类似多进制数的整数，但这种方式存在两个明显局限：一是当列表数量多或元素数量大时，索引容易溢出；二是每次需要反向计算各列表的下标，不如直接生成组合高效。下面提供更优的通用实现思路，以及编程语言内置方案和C++的具体实现：

通用解决方案 #

1. 递归法 #

这是最直观的实现方式，逐层递归处理每个列表，将当前已选择的元素组合与下一个列表的元素逐个拼接，直到遍历完所有列表时执行dosomething：

• 优势：无需预先存储所有组合，边生成边处理，内存占用低；逻辑清晰易理解。
• 核心逻辑：每一层递归负责遍历当前列表的所有元素，将元素加入临时组合后进入下一层递归，递归返回后回溯（移除刚加入的元素），继续处理当前列表的下一个元素。

2. 迭代法 #

从第一个列表的元素出发，逐步与后续列表的元素生成笛卡尔积：

• 初始状态：将第一个列表的每个元素作为单独的初始组合。
• 迭代过程：对每个后续列表，把现有所有组合分别与该列表的每个元素拼接，生成新的组合集合，替换原有集合。
• 优势：避免递归调用的栈开销，适合列表数量较多的场景；如果需要保存所有组合，这种方式可以直接生成完整的组合列表。

编程语言内置功能 #

很多语言提供了现成的笛卡尔积生成工具：

• Python：标准库itertools.product()，直接传入所有列表即可生成迭代器形式的笛卡尔积，例如itertools.product(list1, list2, list3)。
• Java：Guava库的Lists.cartesianProduct()方法，可直接生成所有组合的列表。
• C#：可通过Enumerable.SelectMany嵌套实现，或使用第三方库（如MoreLINQ）的Product方法。

C++ 具体实现 #

递归实现（边生成边处理） #

#include <vector>
#include <iostream>

// 示例处理函数：打印组合
void dosomething(const std::vector<int>& combo) {
    for (size_t i = 0; i < combo.size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << combo[i];
    }
    std::cout << std::endl;
}

// 递归生成笛卡尔积
void generateCartesian(const std::vector<std::vector<int>>& lists, std::vector<int>& current, size_t depth) {
    if (depth == lists.size()) {
        dosomething(current);
        return;
    }
    // 遍历当前层列表的所有元素
    for (int elem : lists[depth]) {
        current.push_back(elem);
        generateCartesian(lists, current, depth + 1);
        current.pop_back(); // 回溯
    }
}

int main() {
    std::vector<std::vector<int>> inputLists = {{1, 2}, {3, 4}, {5, 6}};
    std::vector<int> currentCombo;
    generateCartesian(inputLists, currentCombo, 0);
    return 0;
}

迭代实现（生成所有组合后处理） #

#include <vector>
#include <iostream>

void dosomething(const std::vector<int>& combo) {
    for (size_t i = 0; i < combo.size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << combo[i];
    }
    std::cout << std::endl;
}

std::vector<std::vector<int>> generateCartesian(const std::vector<std::vector<int>>& lists) {
    std::vector<std::vector<int>> result = {{}}; // 初始空组合
    for (const auto& list : lists) {
        std::vector<std::vector<int>> temp;
        // 将现有组合与当前列表元素拼接
        for (const auto& combo : result) {
            for (int elem : list) {
                temp.push_back(combo);
                temp.back().push_back(elem);
            }
        }
        result.swap(temp); // 替换为新的组合集合
    }
    return result;
}

int main() {
    std::vector<std::vector<int>> inputLists = {{1, 2}, {3, 4}, {5, 6}};
    auto allCombos = generateCartesian(inputLists);
    for (const auto& combo : allCombos) {
        dosomething(combo);
    }
    return 0;
}

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