1

再帰を使用する順列関数を書くように依頼されました。関数の唯一のパラメーターは、すべての順列を見つける必要がある文字列でなければなりません。この関数は、考えられるすべての順列を含むベクトルを返す必要があります。next_permutationSTL アルゴリズムで使用できることはわかっていますが、使用しないように求められています。

基本ケースをセットアップしました。for ループが必要であることはわかっていますが、そこからどこに行くべきかよくわかりません。誰かが私を正しい方向に向けることができますか?

vector <string> getPerm(string str)
{
    vector<string> v;
    if(w.length() <= 1)
    {
        v.push_back(str);
        return v;
    }
    else
    {
        for(int i = 0; i < str.size(); i++)
        {
            //Some code
        }
    }
}

どんな助けでも大歓迎です。

4

5 に答える 5

4

関数の前の反復の結果が既にあり、文字列の最初の n-1 要素のすべての順列を返すと想像してください。

vector<string>& v_prev = getPerm(str.substr(0, str.length()-1));

これを

//Some code

あなたのコードの一部。

別のヒント: 再帰の停止条件として長さ 0 の文字列を使用します。長さ 1 の順列を再帰的に構築できます ;)

ソリューション全体は次のとおりです。

vector<string> getPerm(string str)
{
  vector<string> v; 
  if (str.empty())
  {
    v.push_back(string());
    return v;
  }
  else
  {
    vector<string>& v_prev = getPerm(str.substr(0, str.length()-1));
    for(int i = 0; i < v_prev.size(); i++)
    {
      for (int j = 0; j < v_prev[i].length() + 1; j++)
      {
        string p = v_prev[i];
        p.insert(j, str.substr(str.length() - 1, 1));
        v.push_back(p);
      }
    }
    return v;
  }
}
于 2012-10-24T20:47:16.247 に答える
1

文字列「123」のこれらの順列について考えてみてください

123
132

213
231

312
321

そして、これらの「12」の順列について考えてみてください

12
21

nすべての文字の部分文字列の順列がわかっている場合、文字列の順列をどのように構成できるかわかりますかn-1。このタイプのソリューションは再帰的です。

于 2012-10-24T18:17:33.507 に答える
1

Ken Bloom が書いたものを実装する:

vector <string> getPerm(string str)
{
  vector<string> v;
  if(str.length() <= 1)
  {
    v.push_back(str);
    return v;
  }
  else
  {
    for(int i = 0; i < str.size(); i++){
      vector<string> perms = getPerm(str.substr(0,i)+str.substr(i+1));

      for(int j = 0; j < perms.size(); j++){
        v.push_back(str[i] + perms[j]);
      }
    }
  }
}
于 2012-10-24T19:29:43.303 に答える
1
  • の各要素xに対してyourArray
    • yourArray要素なしのコピーを作成しますx。この新しい配列を呼び出しnewArrayます。
    • のすべての順列を見つけるnewArray
    • xこれらの各順列の先頭に 要素を追加します
于 2012-10-24T18:31:01.727 に答える
0

次のようなことを試してください：

permut(s) :
  if s.length=0 : exit;
  else :
    for i=0 to s.length :
      front:=s[i];
      remove(s,i);
      s2 := front + permut(s);
      print s2, NEWLINE;
于 2012-10-24T18:40:36.807 に答える