递归生成任意长度的所有“单词”

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

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

您需要做的就是 "count" 通过可能的单词。给定一个任意词，你将如何转到下一个词？

记住自然数的计数方式。如果你想从 123999 到它的后继 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.

Answer 2

你的递归解有两个错误：

如果需要按字母顺序打印，'a'需要从0开始，而不是相反

只需要最后一层打印，否则重复

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

}

Answer 3

受@fredoverflow 的回答启发，我创建了以下代码，它可以相对更快地完成同样的事情。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>

void printAllPossibleWordsOfLength(char firstChar, char lastChar, int length) {
    char *word = new char[length];
    memset(word, firstChar, length);
    char *lastWord = new char[length];
    memset(lastWord, lastChar, length);
    int count = 0;

    std::cout << word << " -> " << lastWord << std::endl;

    while(true) {
        std::cout << word << std::endl;
        count += 1;
        if(memcmp(word, lastWord, length) == 0) {
            break;
        }
        if(word[length - 1] != lastChar) {
            word[length - 1] += 1;
        } else {
            for(int i=1; i<length; i++) {
                int index = length - i - 1;
                if(word[index] != lastChar) {
                    word[index] += 1;
                    memset(word+index+1, firstChar, length - index - 1);
                    break;
                }
            }
        }
    }

    std::cout << "count: " << count << std::endl;

    delete[] word;
    delete[] lastWord;
}

int main(int argc, char* argv[]) {
    int length;
    if(argc > 1) {
        length = std::atoi(argv[1]);
        if(length == 0) {
            std::cout << "Please enter a valid length (i.e., greater than zero)" << std::endl;
            return 1;
        }
    } else {
        std::cout << "Usage: go <length>" << std::endl;
        return 1;
    }
    clock_t t = clock();
    printAllPossibleWordsOfLength('A', 'Z', length);
    t = clock() - t;
    std:: cout << "Duration: " << t << " clicks (" << ((float)t)/CLOCKS_PER_SEC << " seconds)" << std::endl;
    return 0;
}

递归生成任意长度的所有“单词”

Recursive generation of all “words” of arbitrary length

c++

recursion

nested

permutation

编辑