如何从字符串类型的二维vector生成所有token组合？

你需要实现的是多个字符串集合的笛卡尔积，每个组合用|连接成字符串，结果总数等于所有子vector大小的乘积，同时支持动态扩展子vector。以下是具体实现方式和相关说明：

1. 从头生成完整结果 #

迭代式实现是最高效的方式，避免递归栈溢出，适合处理较大的数据集：

#include <vector>
#include <string>

std::vector<std::string> generateCartesianProduct(const std::vector<std::vector<std::string>>& vecTokens) {
    std::vector<std::string> results;
    if (vecTokens.empty()) return results;

    // 初始化第一个子集合的元素
    for (const auto& token : vecTokens[0]) {
        results.push_back(token);
    }

    // 依次合并后续每个子集合
    for (size_t i = 1; i < vecTokens.size(); ++i) {
        const auto& currentTokens = vecTokens[i];
        std::vector<std::string> temp;
        // 遍历现有结果，与当前子集合的每个元素拼接
        for (const auto& existing : results) {
            for (const auto& token : currentTokens) {
                temp.push_back(existing + "|" + token);
            }
        }
        results.swap(temp); // 用swap减少内存拷贝开销
    }

    return results;
}

2. 增量扩展已有结果 #

如果已经生成了部分结果，新增子vector时无需从头重建，直接对现有结果做扩展：

void extendCartesianProduct(std::vector<std::string>& existingResults, const std::vector<std::string>& newTokens) {
    if (existingResults.empty()) {
        existingResults = newTokens;
        return;
    }
    std::vector<std::string> temp;
    for (const auto& existing : existingResults) {
        for (const auto& token : newTokens) {
            temp.push_back(existing + "|" + token);
        }
    }
    existingResults.swap(temp);
}

3. 递归实现（适合理解逻辑） #

如果数据集不大，递归方式更直观，容易理解笛卡尔积的生成逻辑：

#include <vector>
#include <string>

void buildCartesian(const std::vector<std::vector<std::string>>& vecTokens, size_t currentIndex, std::string currentStr, std::vector<std::string>& results) {
    if (currentIndex == vecTokens.size()) {
        results.push_back(currentStr);
        return;
    }
    for (const auto& token : vecTokens[currentIndex]) {
        std::string nextStr = currentStr.empty() ? token : currentStr + "|" + token;
        buildCartesian(vecTokens, currentIndex + 1, nextStr, results);
    }
}

std::vector<std::string> generateCartesianProductRecursive(const std::vector<std::vector<std::string>>& vecTokens) {
    std::vector<std::string> results;
    buildCartesian(vecTokens, 0, "", results);
    return results;
}

关于标准算法 #

C++标准库中没有直接提供生成笛卡尔积的算法，但这是集合论中的基础操作，核心逻辑就是嵌套遍历多个集合，将元素组合起来。你可以根据自己的需求选择迭代或递归实现，迭代方式在处理大数据量时更稳定。

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