c++ - 如何生成给定长度的字典字符串？

Question

How to generate lexicographical strings of a given length?

我正在寻找一种算法来按字典顺序生成长度为 N 的字符串(字典顺序)。例如给定长度 1，生成的字符串为:"a","b","c","d","e","f",g,h,i,j,k...,z .

对于长度为 2 的字符串，生成的字符串应该是:"aa","ab","ac","ad",...,"ba","bb",...,"zz".

我们如何做到这一点？

这是我所做的:

  void permute(string a, int i, int n, int length)
   {
       int j;
       if (i == length){
           string cand = a.substr(0,length);
              cout<<cand<<endl;
         }

       else
          {
                     for (j = i; j <= n; j++)
                      {
                          swap((a[i]), (a[j]));
                           permute(a, i+1,n,length);
                           swap((a[i]), (a[j]));
                      }
           }
       }

在调用“permute(a,0,a.size(),1)”时字符串 a 如下所示:

aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbccccccccccccccccccccddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeffffffffffffffffffffgggggggggggggggggggghhhhhhhhhhhhhhhhhhhhiiiiiiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkkkllllllllllllllllllllmmmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnnnooooooooooooooooooooppppppppppppppppppppqqqqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrrrssssssssssssssssssssttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzz

生成正确的输出，但它重复字典字符串。如果我将它简化为字母，我相信像“aa”、“aaaa”这样的字符串会被遗漏。那么我们如何解决这个问题，有什么想法吗？

Answer 1

我会递归调用一个简单地循环遍历字母表的函数，并为每个字母放置调用它。

初步测试表明这可能有效:

#include <iostream>
#include <sstream>
#include <string>

void addLetters(std::string base, int tgt_depth)
{
    if (base.length() == tgt_depth) {
        std::cout << base << std::endl;
        return;
    }

    for (char letter = 'a'; letter <= 'z'; ++letter) {
        std::stringstream ss;
        ss << letter;
        addLetters(base + ss.str(), tgt_depth);
    }
}

int main(int argc, char* argv)
{
  // first argument is your "base" -- start with nothing
  // second argument is the depth to which to recurse, i.e. how many letters
  addLetters("", 2);
}