c - 如何找到字符串的所有可能组合？使用 CUDA

Question

我试图通过使用 CUDA 查找字符串的所有可能组合来加快我的算法。实现此目标的最佳方法是什么？
示例:

abc

给出:

a
b
c
ab
ac
bc

到目前为止我什么都没有。我不是要代码。我只是在问最好的方法吗？算法？伪代码？也许讨论？

Answer 1

使用 CUDA 的优势是大规模并行处理，可能有数千个线程，开销很小。为此，您必须想出一种方法，将问题分成小块，而不过分依赖线程之间的通信。在这个问题中，您有 n 个字符，每个输出字符串中的每个字符都可以存在或不存在。这会产生 2^n 总输出字符串。 (您已经从列表中删除了空字符串和原始字符串……如果这是所需的结果，那么您的输出字符串总数为 2^n - 2。)

无论如何，您可以划分创建字符串工作的一种方法是为每个可能的输出字符串分配一个数字，并让每个线程为特定范围的数字计算输出字符串。如果您查看每个数字的二进制表示形式，那么从数字到输出字符串的映射就很容易了。 n 位数中的每个二进制数字对应于长度为 n 的字符串中的一个字符。因此，对于您的示例，二进制中的数字 5 或 101 映射到字符串 "ac"。您列出的字符串将通过计算从 1 到 6 的数字映射来创建，如下所示:

1      c
2      b
3      bc
4      a
5      ac
6      ab

如果需要，您可以计算 7 以获得 abc 或计算 0 以获得空字符串。

除非您对超过十几个字符的单词执行此操作，否则我不确定这会快得多。如果您为超过 25 个字符的单词执行此操作，您可能会开始遇到内存限制，因为您将处理数百兆字节。