-4

26 文字 (26*25*24=15,600 になります) を使用して、可能なすべての 3 文字順列を計算しようとしています。文字の順序は重要であり、文字を繰り返したくありません。(順列を辞書順に生成したかったのですが、それは必須ではありません)

forこれまでループをネストしようとしましたが、可能なすべての組み合わせを反復することになりました。そのため、繰り返し文字がありますが、これは望ましくありません。またfor、3 文字以上が必要な場合、ループの管理が難しくなる可能性があります。

使用されていない文字が得られるまで文字をめくることはできますが、辞書順ではなく、使用するよりもはるかに遅くなりますnext_permutation(このstd方法は使用できません。 26文字）。

これを行うより効率的な方法はありますか？非効率性をnext_permutation考慮して、最初の 6 桁を瞬時に反復します。ただし、この方法を使用して 3 文字の順列をすべて取得するには数秒かかり、next_permutation計算しなければならない 2^n サブセットを使用するとすぐに非効率になります。

ネストされたforループについて私が持っているものは次のとおりです。

char key[] = {'a','b','c','d','e','f','g','h','i','j','k',
'l','m','n','o','p','r','s','t','u','v','w','x','y','z'};
bool used[25];
ZeroMemory( used, sizeof(bool)*25 );

for( int i = 0; i < 25; i++ )
{
     while( used[i] == true )
          i++;
     if( i >= 25 )
          break;
     used[i] = true;
     for( int j = 0; j < 25; j++ )
     {
          while( used[j] == true )
               j++;
          if( j >= 25 )
               break;
          used[j] = true;
          for( int k = 0; k < 25; k++ )
          {
               while( used[k] == true )
                    k++;
               if( k >= 25 )
                    break;
               used[k] = true;

               cout << key[i] << key[j] << key[k] << endl;

               used[k] = false;
          }
          used[j] = false;
     }
     used[i] = false;
}
4

4 に答える 4

6

  1. 組み合わせの開始を表すルートを作成するため、値はありません。

  2. 可能なすべての子を計算します (26 文字、26 子...)

  3. ルートの子ごとに、可能な子を計算します（つまり、残りの文字）

  4. 再帰的限定深度検索を使用して、組み合わせを見つけます。

于 2013-07-30T14:43:05.107 に答える
4

これは、「シンプルな」ソリューションが必要な場合に試すソリューションです。これがどれほどリソースを集中的に使用するかはわかりませんので、小さな文字セットから試してみることをお勧めします。

a = {a...z}
b = {a...z}
c = {a...z}

for each(a)
{
  for each(b)
  {
    for each(c)
    {
     echo a + b + c;
    }
  }
}
于 2013-07-30T14:44:22.103 に答える
3

あなたが持っているような特定の小さなn個の手動ループの場合、最も簡単な方法です。ただし、コードは非常に単純化できます。

for(char a='a'; a<='z'; ++a) {
    for(char b='a'; b<='z'; ++b) {
        if (b==a) continue;
        for(char c='a'; c<='z'; ++c) {
            if (c==a) continue;
            if (c==b) continue;
            std::cout << a << b << c << '\n';
        }
    }
}

変数 N の場合、明らかに別の戦略が必要です。そして、信じられないほど異なる戦略が必要であることが判明しました。これは、再帰を使用して後続の文字を生成するという DaMachk の回答に基づいています。

template<class func_type> 
void generate(std::string& word, int length, const func_type& func) {
    for(char i='a'; i<='z'; ++i) {
        bool used = false;
        for(char c : word) {
            if (c==i) {
                used = true;
                break;
            }
        }
        if (used) continue;
        word.push_back(i);
        if (length==1) func(word);
        else generate(word, length-1, func);
        word.pop_back();
    }
}
template<class func_type> 
void generate(int length, const func_type& func) {
    std::string word;
    generate(word, length, func);
}

ここで見ることができます

アンロール バージョンも作成しました。これは非常に複雑であることが判明しましたが、大幅に高速化されています。2 つのヘルパー関数があります。「次の文字を検索する」( と呼ばれるnext_unused) 関数があります。これは、次の未使用の文字のインデックスで文字を増やすfalseか、できない場合は戻ります。3 番目の関数はreset_range、特定のインデックスから文字列の末尾までの範囲の文字を、可能な限り最初の未使用の文字に「リセット」します。まずreset_range、最初の文字列を見つけるために使用します。後続の文字列を見つけるために、呼び出しますnext_unused最後の文字で、それが失敗した場合は最後から 2 番目の文字、それが失敗した場合は最後から 3 番目の文字などです。適切に増加できる文字が見つかったら、その文字の右側にあるすべての文字を「リセット」します。それを未使用の最小値にします。最初の文字までたどり着き、それを増やすことができない場合は、最後に到達したことになり、停止します。コードは恐ろしいですが、私が理解できる最高のものです。

bool next_unused(char& dest, char begin, bool* used) {
    used[dest] = false;
    dest = 0;
    if (begin > 'Z') return false;
    while(used[begin]) {
        if (++begin > 'Z')
            return false;
    }
    dest = begin;
    used[begin] = true;
    return true;
}
void reset_range(std::string& word, int begin, bool* used) {
    int count = word.size()-begin;
    for(int i=0; i<count; ++i)
        assert(next_unused(word[i+begin], 'A'+i, used));
}
template<class func_type>
void doit(int n, func_type func) {
    bool used['Z'+1] = {};
    std::string word(n, '\0');
    reset_range(word, 0, used);
    for(;;) {
        func(word);
        //find next word
        int index = word.size()-1;
        while(next_unused(word[index], word[index]+1, used) == false) {
            if (--index < 0)
                return; //no more permutations
        }
        reset_range(word, index+1, used);
   }
}

これが仕事中です。
そしてここでは、単純なものの 4 分の 1 の時間で実行されています

于 2013-07-30T20:53:38.057 に答える
0

私はpowershellで同様のことをしていました。9 つのシンボルのすべての可能な組み合わせを生成します。試行錯誤の末、たどり着いたのがこれです。

$S1=New-Object System.Collections.ArrayList
$S1.Add("a")
$S1.Add("b")
$S1.Add("c")
$S1.Add("d")
$S1.Add("e")
$S1.Add("f")
$S1.Add("g")
$S1.Add("h")
$S1.Add("i")
$S1 | % {$a = $_
    $S2 = $S1.Clone()
    $S2.Remove($_)
    $S2 | % {$b = $_
        $S3 = $S2.Clone()
        $S3.Remove($_)
        $S3 | % {$c = $_
            $S4 = $S2.Clone()
            $S4.Remove($_)
            $S4 | % {$d = $_
                $S5 = $S4.Clone()
                $S5.Remove($_)
                $S5 | % {$e = $_
                    $S6 = $S5.Clone()
                    $S6.Remove($_)
                    $S6 | % {$f = $_
                        $S7 = $S6.Clone()
                        $S7.Remove($_)
                        $S7 | % {$g = $_
                            $S8 = $S7.Clone()
                            $S8.Remove($_)
                            $S8 | % {$h = $_
                                $S9 = $S8.Clone()
                                $S9.Remove($_)
                                $S9 | % {$i = $_
                                    ($a+$b+$c+$d+$e+$f+$g+$h+$i)
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
于 2013-08-24T09:02:55.343 に答える