c++ - 在 C++ 中用递归替换 N 级 for 循环

Question

一段时间以来，我一直在尝试想出一种方法来计算单词字符串的所有各种组合。不过，与网络上的大多数组合方法不同，该算法必须生成每个组合，包括所有组合元素不在一个组合中的组合。即，如果我组合“Hello”、“New”和“World”，我正在寻找的组合是:

HelloNewWorld
HelloNew
HelloWorld
Hello
NewWorld
New
World

我大学的一位教授确实想出了一个快速而肮脏的解决方案来做到这一点，但它使用了嵌套的 for 循环。

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

int main()
{
std::vector<std::array<std::string, 2>> vec(3);
vec[0] = {"Hello", ""};
vec[1] = {"New", ""};
vec[2] = {"World", ""};
for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++)
            std::cout << vec[0][i] + vec[1][j] + vec[2][k] << std::endl;
}

正如您可能想象的那样，我想要一种方法来使它实际上有点可用和可移植。我知道这可以通过递归实现，我只是不知道如何实现它。最理想的是，如果可能的话，我想使这个尾递归，因为计划是计算非常大的组合。递归执行此操作的最佳方法是什么？使尾递归容易吗？

Answer 1

在每个级别上，当它到达所有单词的末尾时，它会递归使用和不使用当前单词打印结果:

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

void recurse(std::vector<std::string> &values,size_t level,std::string str) {
  if (level<values.size()) {
    recurse(values,level+1,str+values[level]);
    recurse(values,level+1,str);
  } else {
    std::cout<<str<<"\n";
  }
}

int main(int argc, char*argv[]) {
  if (argc<2)
    std::cout<<argv[0]<<" <word> [<word> [...]]\n";
  else {
    std::vector<std::string> values;
    for(int i=1;i<argc;++i) {
      values.push_back(argv[i]);
    }
    recurse(values,0,"");
  }
  return 0;
}

当使用 ./a.out Hello New World 运行时产生:

HelloNewWorld
HelloNew
HelloWorld
Hello
NewWorld
New
World