非递归实现二维字符串向量的所有组合（C++）

嘿，我懂你要的需求——不用递归，还能处理任意数量的子数组，生成每个子数组各取一个元素的所有组合对吧？这本质上就是求多个集合的笛卡尔积，用迭代的方式完全能搞定，下面给你具体的思路和代码：

核心思路 #

咱们可以用一个计数器数组来模拟“数字进位”的逻辑：

• 每个计数器对应一个子数组，记录当前取到该子数组的第几个元素
• 初始时所有计数器都设为0，对应第一个组合（每个子数组的第一个元素）
• 每次尝试把最后一个计数器加1，如果超过对应子数组的长度，就把它归0，然后前一个计数器加1，以此类推，就像十进制数满10进位一样
• 直到所有计数器都到达对应子数组的最后一个索引，就停止生成

完整C++代码实现 #

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<vector<string>> generateAllCombinations(const vector<vector<string>>& input) {
    vector<vector<string>> result;
    
    // 处理空输入的边界情况
    if (input.empty()) {
        return result;
    }
    
    // 初始化计数器数组，每个子数组初始取第0个元素
    vector<int> counters(input.size(), 0);
    int totalArrays = input.size();
    
    while (true) {
        // 生成当前计数器对应的组合
        vector<string> currentCombination;
        for (int i = 0; i < totalArrays; ++i) {
            currentCombination.push_back(input[i][counters[i]]);
        }
        result.push_back(currentCombination);
        
        // 处理进位逻辑，从最后一个子数组开始
        int index = totalArrays - 1;
        while (index >= 0) {
            counters[index]++;
            // 如果当前计数器没超出子数组长度，进位结束
            if (counters[index] < input[index].size()) {
                break;
            }
            // 否则归0，继续向前进位
            counters[index] = 0;
            index--;
        }
        
        // 如果index变成-1，说明所有计数器都进位完成，循环终止
        if (index < 0) {
            break;
        }
    }
    
    return result;
}

// 测试函数
int main() {
    vector<vector<string>> input = {
        {"red", "wooden", "gate"},
        {"lazy", "little", "man"},
        {"what", "where", "who", "why"}
    };
    
    vector<vector<string>> combinations = generateAllCombinations(input);
    
    // 输出所有组合
    for (const auto& comb : combinations) {
        for (const auto& str : comb) {
            cout << str << " ";
        }
        cout << endl;
    }
    
    return 0;
}

代码细节解释 #

1. 边界处理：先判断输入是否为空，避免后续操作出现数组越界等错误
2. 计数器初始化：用vector<int>保存每个子数组当前的索引，初始值全为0，对应第一个组合
3. 组合生成：每次循环根据计数器从每个子数组取出对应元素，组成当前组合并加入结果集合
4. 进位逻辑：从最后一个计数器开始递增，一旦超出子数组长度就归0并向前一位进位，直到找到可以递增的计数器或者所有计数器都处理完毕（index变为-1）
5. 终止条件：当index小于0时，说明所有可能的组合都已生成，退出循环

示例输出片段 #

运行上面的代码，会输出你需要的所有组合，比如：

red lazy what 
red lazy where 
red lazy who 
red lazy why 
red little what 
red little where 
...（中间省略其他组合）
gate man why 

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