c++ - 并行算法产生一个集合的所有可能序列

Question

我在尝试生成给定字符集的所有可能字符串时遇到困难。设 S 为一组符号。我需要处理长度为 n 的 S 的所有可能组合。例如，如果 S={'a','b','+','-'} 和 n=4 算法应处理以下序列:

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

目前我的算法是下面描述的非高效递归算法。我有两个问题:

1. 有没有更快的算法？
2. 是否有解决这个问题的并行算法？

当前实现:(简化)

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

您的算法看起来已经非常高效，您没有浪费任何工作。唯一可能稍微改进的是递归导致的函数调用开销。但是递归很好，因为它可以轻松并行化:

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

例如，确保使用 C++11 特性和线程进行编译

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

此版本的函数将按顺序枚举最大长度为 split_depth 的所有前缀，然后生成一个线程以进一步处理其中的每一个。因此，它将总共启动 |S|^split_depth 个线程，您可以对其进行调整以匹配您的硬件并发性。