c++ - 递归生成任意长度的所有 “words”

Question

我有一个工作函数可以生成所有可能的特定长度的“单词”，即

AAAAA
BAAAA
CAAAA
...
ZZZZX
ZZZZY
ZZZZZ

我想概括此函数以适用于任意 长度。

在下面的可编译C++代码中
iterative_generation() 是工作函数和
recursive_generation() 是 WIP 替换。

请记住，这两个函数的输出不仅略有不同，而且是镜像的(这对我的实现并没有真正的影响)。

#include <iostream>
using namespace std;

const int alfLen = 26; // alphabet length
const int strLen = 5;  // string length
char word[strLen];     // the word that we generate using either of the
                       // functions
void iterative_generation() {          // all loops in this function are
    for (int f=0; f<alfLen; f++) {     // essentially the same
        word[0] = f+'A';
        for (int g=0; g<alfLen; g++) {
            word[1] = g+'A';
            for (int h=0; h<alfLen; h++) {
                word[2] = h+'A';
                for (int i=0; i<alfLen; i++) {
                    word[3] = i+'A';
                    for (int j=0; j<alfLen; j++) {
                        word[4] = j+'A';
                        cout << word << endl;
                    }
                }
            }
        }
    }
}

void recursive_generation(int a) {
    for (int i=0; i<alfLen; i++) { // the i variable should be accessible
        if (0 < a) {               // in every recursion of the function
            recursive_generation(a-1); // will run for a == 0
        }
        word[a] = i+'A';
        cout << word << endl;
    }
}

int main() {
    for (int i=0; i<strLen; i++) {
        word[i] = 'A';
    }
    // uncomment the function you want to run
    //recursive_generation(strLen-1); // this produces duplicate words
    //iterative_generation(); // this yields is the desired result
}

我认为问题可能在于我在所有递归中使用了相同的 i 变量。在迭代函数中，每个 for 循环都有自己的变量。

具体的后果是什么，我不能说，但是递归函数有时会产生重复的单词(例如 ZAAAA 连续出现两次，而 **AAA 生成两次)。

你能帮我改一下递归函数，让它的结果和迭代函数的结果一样吗？

编辑

我意识到我只需要打印最内层函数的结果。这是我将其更改为:

#include <iostream>
using namespace std;

const int alfLen = 26;
const int strLen = 5;
char word[strLen];

void recursive_generation(int a) {
        for (int i=0; i<alfLen; i++) {
                word[a] = i+'A';
                if (0 < a) {
                        recursive_generation(a-1);
                }
                if (a == 0) {
                        cout << word << endl;
                }
        }
}

int main() {
        for (int i=0; i<strLen; i++) {
        word[i] = 'A';
        }
        recursive_generation(strLen-1);
}

Answer 1

事实证明你根本不需要递归来将你的算法推广到任意长度的单词。

您需要做的就是“数”出可能的单词。给定一个任意词，你将如何转到下一个词？

记住自然数是如何计算的。如果你想从 123999 到它的后继 124000，你用零替换尾随的九，然后递增下一个数字:

123999
     |
123990
    |
123900
   |
123000
  |
124000

请注意我们如何将数字视为从 0 到 9 的数字串。我们可以对字符串使用与其他字母完全相同的想法，例如从 A 到 Z 的字母表:

ABCZZZ
     |
ABCZZA
    |
ABCZAA
   |
ABCAAA
  |
ABDAAA

我们所做的只是用 As 替换尾随的 Zs，然后递增下一个字符。没什么神奇的。

我建议您现在自己用 C++ 实现这个想法。为了比较，这是我的解决方案:

#include <iostream>
#include <string>

void generate_words(char first, char last, int n)
{
    std::string word(n, first);
    while (true)
    {
        std::cout << word << '\n';
        std::string::reverse_iterator it = word.rbegin();
        while (*it == last)
        {
            *it = first;
            ++it;
            if (it == word.rend()) return;
        }
        ++*it;
    }
}

int main()
{
    generate_words('A', 'Z', 5);
}

如果您想改为从左到右计数(正如您的示例所暗示的那样)，只需将 reverse_iterator 替换为 iterator, rbegin begin 和 rend end。