Parallel algorithm to produce all possible sequences of a set

Question

I'm having difficult time while trying to produce all possible strings of a given character set. Let S be set of symbols. I need to process all possible combinations of S in length n. For example if S={'a','b','+','-'} and n=4 the algorithm should process following sequences:

aaaa
aaab
abab
+aa-
// And all other sequences in the universe

Currently my algorithm is a non-efficient recursive algorithm described below. I have two question:

1. Is there a faster algorithm?
2. Is there a parallel algorithm to solve this problem?

Current implementation: (Simplified)

void workhorse(vector<char> &input, vector<char>::iterator i)
{
    if(i==inputs.end()) {
        // process the input
        return;
    }
    else {
        for( const auto& symbol : S) {
            *i=symbol;
            workhorse(input, i+1);
        }
    }
}   

Answer 1

Your algorithm already looks pretty efficient, you're not wasting any work. The only thing that could probably be improved slightly is the function call overhead due to recursion. But recursion is good, because it allows for easy parallelization:

#include <thread>
#include <array>
#include <string>
#include <vector>
using namespace std;

array<char,3> S = {{ 'a', 'b', 'c' }};
const int split_depth = 2;
void workhorse(string& result, int i) {
    if (i == result.size()) {
        // process the input
        return;
    }
    if (i == split_depth) {
        vector<thread> threads;
        for (char symbol : S) {
            result[i] = symbol;
            threads.emplace_back([=] {
                string cpy(result);
                workhorse(cpy, i + 1);
            });
        }
        for (thread& t: threads) t.join();
    } else {
        for (char symbol : S) {
            result[i] = symbol;
            workhorse(result, i + 1);
        }
    }
}

int main() {
    string res(6, 0);
    workhorse(res, 0);
}

Make sure to compile it with C++11 features and threading enabled, for example

$ g++ -O3 -std=c++11 -lpthread [file].cpp

This version of the function will enumerate all prefixes of up to length split_depth sequentially and then spawn a thread to further process each of those. So it will start |S|^split_depth threads in total, which you can adapt to match your hardware concurrency.