4

サイズ X のセットのサイズ Y のすべての順列を計算したいと思います。つまり、(1,2,3) があり、サイズ 2、3P2 のすべての順列が必要な場合、(1,2) になります ( 1,3) (2,1) (2,3) (3,1) (3,2)。

GSL と C++ STL はどちらも、私が見ることができる xPx しか提供していません。誰かがこれを行うことができる C/C++ ライブラリを教えてくれますか、または高速でメモリ効率の良いアルゴリズムを詳しく説明してくれますか?

非常に短い暗号文を解こうとしています。私は 2 つの文字を理解し、ブルート フォース アタックを行うことにしました。私は「ouglg ouyakl」を持っており、すべての順列を非常に優れた辞書と照合しています。2 文字を削除したので、24P7 または 1,744,364,160 の可能性がありますが、それほど悪くはありません。私は現在 Perl プログラムを実行しているので、これはプログラミング時間 + 実行時間の合計効率の興味深いテストになるでしょう。:)

（いいえ、暗号文の答えだけが欲しいわけではありません。）

4

3 に答える 3

2

私は以前にこのライブラリを（C ++であることに注意してください）同様のことをする必要のあるコードで使用しました。繰り返しの有無にかかわらず、順列と組み合わせがあります。あなたの問題については、これで十分です（テストされていません...）：

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

std::vector<int>::iterator first = v.begin(), middle = v.begin() + 2, last = v.end();

do {
    // do stuff with elements in range first...middle (but dont change them)
} while(next_partial_permutation(first, middle, last));
于 2009-11-02T22:11:40.890 に答える
0

フラグのを使用std::next_permutation()して組み合わせを取得できます。vector<bool>から2つの要素を選択する例をとると(1,2,3)、ベクトルをとして開始します(false, true, true)。これを繰り返すと、最初からやり直す前に、がnext_permutation()得られます。(true, false, true)(true, true, false)

組み合わせではなく順列が必要なため、各組み合わせを実際の要素のセットにマップし（たとえば(true, false, true)、（1、3）になります）、を使用してこれらのすべての順列を生成しnext_permutation()ます。

于 2009-11-02T23:55:54.047 に答える
0

暗号に関するあなたの質問は正確にはわかりません。しかし、辞書でこの単語の最長順列 (アナグラム) を見つけたい場合は、彼の方法を試すことができます。

  1. あなたの単語のビットマスクを作成します。おそらく 64 ビット演算を使用できるため、内部にほぼ 3 つのアルファベットを収めることができます。

a-> 最初のビット、b-> 2 番目のビットなど。「ouglg ouyakl」ケースに単語がある場合、これは意味します

 abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop
 100000100011001000001001000000010000100100000100000000000000000000

(何かを見逃していないことを願っています) これで、ボキャブラリ用に同じビットマスクを作成できます。

語彙をチェックするときは、

 vocabulary & ( ouglg_ouyakl ^ vocabulary)

語彙がouglg_ouyaklからのものである場合、これは0になります。

順列について

for each permutation of numbers fom  1-n // that is 1,2 and 2,1
  for(i=0;i<end;i++)
    for(j=i+1;j<end;j++)
      SET[permutation[i]],SET[permutation[j]]

編集: 以前のソリューションは 24P7 には不適切でした。

于 2009-11-02T22:50:02.167 に答える