c++ - 在二维数组的每一行中查找具有 1 个元素的所有可能组合

Question

最近我一直在尝试做一个问题，要求我从每一行中只选择一个元素来找到所有不同的组合。例如，我输入 n 行，每行 2 个字符串。但是，我只想找到我从每行中选择 1 个字符串的所有不同组合。

例子:

输入:

3
alex bob
straw mat
eat drink

示例组合: 亚历克斯吸管饮料

这会产生 2^n 种组合，在本例中为 2^3 = 8 种组合。但是，如果我要使用 n for 循环来查找组合 例如

#include <iostream>
#include <cstring>
#include <string>

using namespace std;
int n;
int main(int argc, char ** argv) {

    cin >> n; //rows of words
    string words[n][2]; //the words with 2 words per row

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> words[i][j]; //input of words
        }
    }
    //finding all possible combinations
    for (int i =0; i<n; i++){
        for (int j=0; j<2; j++){
            for (int x=0; x<2; x++){
                //and so on per n
            }
        }
    }
    return 0;
}

这将需要 n 个 for 循环来找出数组的所有组合，每行只取一个项目。找到大小为 n 的所有不同组合的最佳和最简单的方法是什么，因为我会从每行的两个字符串中取出一个字符串？谢谢。

Answer 1

你可以做递归。

假设 C++11，可能是这样的(虽然没有尝试编译它):

// finding all possible combinations
std::vector<std::vector<std::string>> combinations;

const auto processLine = [&](const std::vector<std::string>& currentCombination, int line) {    

    std::vector<std::string> combination0 = currentCombination;
    std::vector<std::string> combination1 = currentCombination;
    combination0.push_back(words[line][0]);
    combination1.push_back(words[line][1]);

    if (line + 1 < n) {
        // process next line
        processLine(combination0, line + 1);
        processLine(combination1, line + 1);
    }
    else {
        // last line - keep the result
        combinations.push_back(combination0);
        combinations.push_back(combination1);
    }
};

std::vector<std::string> empty;
processLine(empty, 0);

// print results
for (const auto& combination : combinations) {
    for (const auto& word : combination) {
        std::cout << word << " ";
    }
    std::cout << std::endl;
}