2

最小量と最大量の 1 を指定して、長さ n の 0 と 1 のすべての組み合わせを生成する効率的なアルゴリズムがあるかどうかを知りたいです。

例：

n=4 最小=2 最大=3

0011 0101 1001 0110 1010 1100 (with 2 1's)
0111 1011 1101 1110           (with 3 1's)

(n-min)*0(min)*1 から (max)*1 (n-max)*0 (例では 0011 から 1110 まで) のバイナリで数えることができ、制約がありますが、より効率的なアルゴリズムがあるかどうかを知りたいです。

4

1 に答える 1

2

nサイズと1の組み合わせを繰り返す単純なアルゴリズムがありkます。

  1. 長さ のビット ベクトルから始めます。n最後のkビットは1です。
  2. 可能な限り繰り返します (つまりn、最初のkビットがである長さのビット ベクトルを取得するまで1): 01ビット ベクトルの最後のシーケンスを見つけます。に変更し10、次のすべての1ビット (すぐ後にある必要があります) をシーケンスの最後に移動します。

これを行うには、単純なループのないビット操作ハックがあります。この質問に対する私の答えでそれを見ることができます: Find n-th set of powerset

于 2013-06-02T21:56:45.613 に答える