0

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

我正在寻找一种算法来按字典顺序生成长度为 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”这样的字符串会被遗漏。那么我们如何才能解决这个问题，有什么想法吗？

4

3 回答 3

7

我会对一个简单地遍历字母表的函数进行递归调用，并为每个字母位置调用它。

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

#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);
}
于 2013-02-28T16:25:44.657 回答
1

假设您想按这些字符串的字典顺序查看哪个字符串位于 M 位置，请以 26 为基数表示此数字，然后将 0 映射到 a，1 映射到 b，依此类推。您必须在左侧添加零（或 as），直到字符串达到所需的长度。现在要解决您的问题，只需遍历整数（最多为长度为 N 的字符串的数量，即 26 N）并应用我建议的转换。

于 2013-02-28T16:28:01.530 回答
0 
for(i='a';i<='z';i++)
{
    recur(new String(i));
}
void recur(String s)
{
   if(s.length()==dig)
   {
       add s to array
       return
   }
   for(i='a';i<='z';i++)
       recur(s+i);

}

尽管此代码不足以生成超过 5 位数字，因为有 26 ^ dig 可能性。而且我不知道 c++，所以我已经编写了算法。但我觉得其中没有什么是编码器 ia 语言无法转换的

于 2013-02-28T16:30:51.827 回答