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);

}

このコードは、26^dig の可能性があるため、5 桁以上を生成するのに十分ではありませんが、c++ を知らないので、アルゴリズムを作成しました。しかし、コーダーや言語が変換できないものは何もないと感じています

于 2013-02-28T16:30:51.827 に答える