在不使用递归的情况下解决所有2d字符串向量组合？(C++)

Question

问题是:

创建一个函数来计算字符串数组的所有组合,例如:{ { "red", "wooden", "gate" }, { "lazy", "little", "man" }, { "what", "where", "who", "why" } }输出:red lazy what,red lazy where,red lazy who,red lazy why,red little what,etc .....

此函数将打印第一个数组中一个字的所有组合,第二个数组中的一个字,第三个数组中的一个字等.

您的解决方案可能不使用递归

注意:每个阵列中的数组数和元素数可能会有所不同!您的方法需要能够处理此问题.

---

我正在尝试练习我的算法,这个问题只会让我发疯.我曾经尝试过集思广益,但此时已经花了好几个小时无处可去.当我想到我可能只需要创建一个字符串向量时,我正在将我的思想重新设计到另一个嵌套循环(见下文......)中,这可能会成为一个非常大的向量...现在,我们称之为矢量endings).如果我在给定的外部向量中向后遍历vector<vector<string>>并endings通过将每个结尾附加到当前外部向量中的每个字符串来更新,那么当我到达第一个外部向量时,我的所有组合都将在endings.

我可能没有想到这个,因为我假设我只是打印,我不应该存储这么多.无论如何,这里有一些拙劣的代码,我停止发布这个.这并不多.

vector<vector<string>> ar = {{"red", "wooden", "gate"}, 
                             {"lazy", "little", "man"}, 
                             {"what", "where", "who", "why"}};

vector<string> res(ar.size());

for (int i = 0; i < ar.size(); i++) {   
    res[i]= ar[i][0];
}

int i;

for (i = ar.size()-1; i > 0; i--) {
    for (int j = arr.size()-1-i, j > arr.size()-1-i; j--) {
                // ...
    }
}

让我知道你是如何建议解决这个问题的.

Answer 1

"计算机科学中的所有问题都可以通过另一层次的间接解决" - 大卫惠勒

https://en.wikipedia.org/wiki/Indirection

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

void print(std::vector<std::vector<std::string>> const& astrs, std::vector<std::size_t> const& idxs)
{
    const char* sep = "";
    for(std::size_t i = 0 ; i < astrs.size() ; ++i)
    {
        std::cout << sep << astrs[i][idxs[i]];
        sep = ", ";
    }
    std::cout << '\n';
}

bool next_in_sequence(std::vector<std::vector<std::string>> const& astrs, std::vector<std::size_t>& idxs)
{
    for(std::size_t i = astrs.size() ; i-- ; )
    {
        if(++idxs[i] != astrs[i].size())
        {
            return true;
        }
        idxs[i] = 0;
    }

    return false;
}

int main()
{
    std::vector<std::vector<std::string>> const ar = {
        {"red", "wooden", "gate"}, 
        {"lazy", "little", "man"}, 
        {"what", "where", "who", "why"}
    };

    vector<std::size_t> idxs(ar.size(), 0);

    do
    {
        print(ar, idxs);
    }
    while(next_in_sequence(ar, idxs));
}

该解决方案构建了一系列的indecies.可以将此数组视为一个整数,其中每个数字列都有自己的基数.基数是ar+ 1中相应"槽"中的字符串数.

我们需要做的就是"递增""整数"直到它换行.这是在函数中执行的next_in_sequence().

这是表达这个想法的另一种方式.它在概念上效率较低(实际上,可能不是'小'输入集),但反过来演示了这个想法 - 计算最大组合数,迭代每个组合并计算我们的多基索引的'数字'代表我们去.它不需要额外的存储,代价是重复计算:

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

std::size_t combinations_at(std::vector<std::vector<std::string>> const& astrs, std::size_t col)
{
    std::size_t result = 1;
    while (col != astrs.size())
    {
        result *= astrs[col].size();
        ++col;
    }
    return result;
}

void print(std::vector<std::vector<std::string>> const& astrs, std::size_t which)
{
    const char* sep = "";
    for(std::size_t col = 0 ; col != astrs.size() ; ++col)
    {
        auto nextmod = combinations_at(astrs, col + 1);
        auto i = which / nextmod;
        which %= nextmod;
        std::cout << sep << astrs[col][i];
        sep = ", ";
    }
    std::cout << '\n';
}

int main()
{
    std::vector<std::vector<std::string>> const ar = {
        {"red", "wooden", "gate"},
        {"lazy", "little", "man"},
        {"what", "where", "who", "why"}
    };

    const auto limit = combinations_at(ar, 0);
    for(std::size_t i = 0 ; i < limit ; ++i)
        print(ar, i);
}