给定长度的英文字母的排列

Question

所以我有这段代码。不确定它是否有效，因为该程序的运行时间仍在继续。

void permute(std::vector<std::string>& wordsVector, std::string prefix, int     length, std::string alphabet) {
if (length == 0) {
    //end the recursion
    wordsVector.push_back(prefix);
}
else {
    for (int i = 0; i < alphabet.length(); ++i) {
        permute(wordsVector, prefix + alphabet.at(i), length - 1, alphabet);
    }
}}

我正在尝试获取给定长度的英文字母表中的所有字符组合。我不确定目前的方法是否正确。

Alphabet 由长度为 26 的字符串中的 A-Z 组成。WordsVectors 包含单词的所有不同组合。前缀意味着递归传递，直到生成一个单词并且长度不言自明。

例如，如果我给函数的长度为 7，如果我是正确的，我期望大小为 26 x 25 x 24 x 23 x 22 x 21 x 20 = 3315312000，遵循排列公式。我认为程序不应该运行这么长，所以要么我遇到了无限循环，要么我的方法有问题。请指教。谢谢

Answer 1

我认为您在堆栈上执行此操作可能会有很大的问题。您递归执行的大部分计算，这意味着每次为函数分配 space。

尝试线性重新表述。我想我以前也遇到过这样的问题。

Answer 2

堆栈肯定会溢出但是专注于你的问题即使你写一个迭代程序也需要很长时间（不是无限循环只是很长）

[26L, 650L, 15600L, 358800L, 7893600L, 165765600L, 3315312000L, 62990928000L, 1133836704000L, 19275223968000L, 308403583488000L, 4626053752320000L, 64764752532480000L, 841941782922240000L, 10103301395066880000L, 111136315345735680000L, 1111363153457356800000L, 10002268381116211200000L, 80018147048929689600000L, 560127029342507827200000L, 3360762176055046963200000L, 16803810880275234816000000L, 67215243521100939264000000L, 201645730563302817792000000L, 403291461126605635584000000L, 403291461126605635584000000L]

以上列表是1<=n<=26的可能性数。您可以看到随着 n 的增加，可能性的数量大大增加。假设您有 1GHz 处理器，每秒执行 10^9 次操作。假设考虑 n=26 其 403291461126605635584000000L 的可能性数量。很明显，如果你坐下来列出所有的可能性，它会这么长（这么多年）以至于你会觉得它进入了无限循环。最后我没有仔细研究你的代码，但简而言之，即使你正确地编写它，迭代地并且不存储（再次不能有这么多内存）并且只是打印所有可能性它会花费很长时间才能更大n 的值。

编辑

正如 jaromax 和其他人所说，如果你只想为 n 的较小值编写它，比如说少于 10-12，你可以编写一个迭代程序来 list/print 它们。对于较小的值，它将运行相当快。但是，如果您还想存储它们，那么 n 将不得不说少于 5 说。（实际上取决于有多少 RAM 可用，或者您可以找到一些排列将它们写入磁盘，然后取决于您可以节省多少磁盘内存，再次参考我上面发布的可能性列表的数量。它给出了两个时间的粗略概念和 space 复杂度）。

Answer 3

你的问题暗示你认为有 26x25x24x ... 排列

你的代码没有任何我能看到的东西来避免 "AAAAAAA" 成为一个排列，在这种情况下有 26x26x26x ...

所以除了以 26 为基数的非常复杂的计数方式之外，我认为它也会给出错误的答案？

给定长度的英文字母的排列

Permutations of English Alphabet of a given length

c++

string

permutation

alphabet