7

特定のハミング重みで固定サイズの 2 進数のすべての順列を計算するアルゴリズムが必要です。たとえば、ハミングの重みが 2 で、バイナリ サイズが 4 の場合、次の出力があります。

0011
0110
0101
1100
1010
1001

C(n,r)このような組み合わせの数は、この例のように 6 で計算されC(4,2)ます。

数値を 0 から 2^n に増やすだけでこれを解決できることに注意して、カウントが問題ないかどうかを確認してください。ただし、これは迅速な解決策ではありません。C++ で bitset クラスを使用して問題を解決することを検討しており、N を増やす必要があります。

この問題には明らかな再帰アルゴリズムがあることを付け加えたいと思います。スタックオーバーフローのため、良い答えではありません。ゴスパーのハックからここで良い答えを受け取りました。入力をスケールアップする必要があり、後で MPI 実装を使用する可能性がありますが、スケーラブルなライブラリが必要です。unsigned int は十分に大きくないので、bitset のようなスケーラブルで高速なライブラリが必要です。ビットセット ライブラリに追加がないため、ソリューションはここでは適用できません。他の解決策はありますか？

4

2 に答える 2

5

Gosper's Hackを使用して、「辞書順で次のビット順列」を実装できます。

unsigned int v; // current permutation of bits 
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change, 
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

ctzまたは、 ( _BitScanForwardMSVC に)がない場合は、

unsigned int t = (v | (v - 1)) + 1;  
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);
于 2015-01-03T14:35:46.563 に答える
2

次の方法で生成できます。

  1. 最初に、最初に n - r 個のゼロ、最後に r 個のゼロを持つベクトルを作成します ( 0011n = 4 および r = 2 の場合)。

  2. その後、次の手順を繰り返します。

    1. ゼロが左に配置されるように、最も右のものを見つけます。そのような人がいなければ、私たちは終わりです。
    2. 左に移動します (1 桁分、つまりゼロと入れ替えます)。
    3. それから右側にあるすべてのものをベクトルの最後に移動します。
      たとえば、 がある場合0110、最初に左に移動できる最も右のものを移動して を取得1010し、次にすべてのものをそれからベクトルの最後まで右にシフトして を取得し1001ます。

このソリューションにはO(C(n, r) * n)時間の複雑性があります。このソリューションのもう 1 つの特徴は、要素を辞書順に生成することです。

于 2015-01-03T14:12:33.613 に答える