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

Question

I have been trying for some time now to come up with a way to compute all the various combinations of strings of words for some time now. Unlike most methods for combining on the web though, the algorithm must produce every combination, including those in which all the combined elements aren't in a single combination. ie, if I am combining 'Hello', 'New' and 'World', the combinations I am looking for are:

HelloNewWorld
HelloNew
HelloWorld
Hello
NewWorld
New
World

A professor from my college did come up with a quick and dirty solution for doing just that, but it is using nested for loops.

#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;
}

As you might imagine, I desired a way to make this actually somewhat usable and portable. I know that this is possible with recursion, I just don't know how to implement it. Optimally, I would like to make this tail-recursive if at all possible, as the plan is to compute very large combinations. What would be the best way to do this recursively, and would it be easy to make tail-recursive?

Answer 1

You can do this pretty efficiently by using all combinations from k=1 to k=N for a vector of N elements. Using Howard Hinnant's library available 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;
}

Compiling this with the C++14 standard and running it outputs:

Hello
New
World
HelloNew
HelloWorld
NewWorld
HelloNewWorld

This is exactly what your post described. Since the lambda is a custom functor, and can store state, you can do whatever you would like with the combinations: store a copy, print them, etc.

This is dramatically faster than anything you can get in the standard library without major work, or from suggestions made for the standard library. For example, std::next_combination and std::next_permutation (the former was not included, but was suggested here). I highly suggest reading Howard Hinnant's entirely blog post: it is enlightening. The time complexity on his implementations, and brute speed beats most other suggestions. If you need high performance combinations or permutations, he's already done the work for you.

Answer 2

At each level it recurses both with and without the current word printing the result when it gets to the end of all the words:

#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;
}

Which, when run with ./a.out Hello New World produces:

HelloNewWorld
HelloNew
HelloWorld
Hello
NewWorld
New
World

Answer 3

If the only possibilities is for a word to appear or not appear, that makes two possibilities. So for n words you have 2^n combinations. So you just count through the 2^n numbers from 0 (including) to 2^n-1 (including) and map each bit to one word.

No recursion needed, just one counting for loop.

Answer 4

If i understand this correctly you want to generate all combinations of a string. in that case you can use a BFS along with a set and a queue to generate the combinations, I will try to explain.

Say your string is ABCD. You have a queue to which you add ABCD and a set to which you add ABCD now

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

to generate substrings in step 2 you do the following

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;
}

doing this on ABCD(the input string) will generate BCD,ACD and ABD and ABC. now add those 3 to the set and the queue

now, you add BCD,ACD and ABD to the set. Lets say BCD is queue.front(). You pop that and generate CD,BD and BC and add them to the set and queue. when you pop ACD next, you generate CD,AD and AC but now you wont add CD to the queue because it is in the set.

EDIT:

I see your issue, my answer works for a string but you can use the same principle on a vector<string> to generate all combinations ABCD would just beHello(A)World(B)...