在 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

如果唯一的可能性是一个词出现或不出现，那就有两种可能性。所以对于 n 个单词，你有 2^n 种组合。因此，您只需从 0（包括）到 2^n-1（包括）计算 2^n 个数字，并将每一位映射到一个单词。

不需要递归，只需要一个循环计数。

Answer 2

如果我理解正确，您想要生成一个字符串的所有组合。在这种情况下，您可以使用 BFS 以及集合和队列来生成组合，我将尝试解释。

假设您的字符串是 ABCD。您有一个要添加 ABCD 的队列和一个要添加 ABCD 的集合

while the queue is not empty
1) you pop the top element
2) you generate substrings of that popped element
  a) if that substring is not in the set add it to the queue

要在步骤 2 中生成子字符串，您需要执行以下操作

for(int i =0;i<string.length();i++)
{
  string substr1 = string.substr(0,i);
  string substr2 = string.substr(i,string.length()-1);
  string substring = substr1+substr2;
}

在 ABCD（输入字符串）上执行此操作将生成 BCD、ACD 和 ABD 以及 ABC。现在将这 3 个添加到集合和队列中

现在，您将 BCD、ACD 和 ABD 添加到集合中。假设 BCD 是 queue.front()。您将其弹出并生成 CD、BD 和 BC 并将它们添加到 set 和队列中。当你接下来弹出 ACD 时，你会生成 CD、AD 和 AC，但现在你不会将 CD 添加到队列中，因为它在集合中。

编辑:

我看到了你的问题，我的答案适用于字符串，但你可以在 vector<string> 上使用相同的原理来生成所有组合 ABCD 只是 Hello(A)World(B)...

Answer 3

对于 N 个元素的向量，您可以使用从 k=1 到 k=N 的所有组合来非常有效地完成此操作。使用可用的 Howard Hinnant 库 here, you can use it fairly effectively. In my case, I've named the library sampling.h, which is the only external dependency and can be viewed in it's entirety here。

#include "sampling.h"
#include <iostream>
#include <vector>


/**
 *  This function can take any container that has a bidirectional
 *  iterator (std::list, std::deque, std::vector) that contains elements
 *  of type std::string or similar, that must implement an `operator+`
 *  and `operator<<` for printing.
 */
template <typename BiDirStringContainer>
void print_combinations(BiDirStringContainer& container)
{
    auto first = container.begin();
    auto last = container.end();
    for (size_t i = 1; i <= container.size(); ++i) {
        auto mid = first + i;
        for_each_combination(first, mid, last, [](auto f, auto l) {
            std::string w;
            for (; f != l; ++f) {
                w += *f;
            }
            std::cout << w << std::endl;
            return false;
        });
    }
}


int main(void)
{
    std::vector<std::string> words = {
        "Hello",
        "New",
        "World",
    };
    print_combinations(words);

    return 0;
}

使用 C++14 标准进行编译，运行输出：

Hello
New
World
HelloNew
HelloWorld
NewWorld
HelloNewWorld

这正是您 post 所描述的。由于 lambda 是一个自定义仿函数，并且可以存储状态，因此您可以对这些组合做任何您想做的事情：存储副本、打印它们等。

这比您无需大量工作即可从标准库中获得的任何东西或从对标准库提出的建议中获得的任何东西都要快得多。例如，std::next_combination和std::next_permutation（前者未包含，但被建议为here）。我强烈建议阅读 Howard Hinnant 的整个博客 post：它很有启发性。他的实现的时间复杂度和极速击败了大多数其他建议。如果您需要高性能组合或排列，他已经为您完成了工作。

Answer 4

在每个级别上，当它到达所有单词的末尾时，它会在有和没有当前单词的情况下递归打印结果：

#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

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

Replacing N-level for loops with recursion in C++

c++

recursion

for-loop

tail-recursion