バイナリビットパターンの組み合わせを集計する

Question

n-bitワードのバイナリビットパターンの数が、2^nより小さい任意の制限値以下であるアルゴリズムを探しています。さらに、すべての1-bitの組み合わせ、2-bitの組み合わせなどのカウントを生成したいと思います。明らかに、制限が2^nの場合、2^nの組み合わせ(C(n,1) 1-bit combinations plus C(n,2) 2-bit plus C(n,3) 3-bit and so on)があります。ただし、制限が課せられた場合、その組み合わせのすべてが有効ではありません（課された制限よりも小さい）。

たとえば、n=4とします。可能な16のビットパターンがあり、そのうちの15ビットは1以上の1-bitsを含む。 10を限度とすると、10より大きいパターンはカウントに含まれません。したがって、単一ビットパターンの場合、有効なビットパターンは0001,0010,0100、および1000となります。 2ビットのパターンは、0011,0101,0110,1001となる。パターン1010および1100は10を超えているためカウントされません。唯一の3ビットのビットは0111で、唯一の4ビットパターン1111は限界を超えています。

Fが私のカウント機能がある場合、F(4,10,1)は4を返す、C(4,2) 6. nの実際の値が大きくなる可能性があるためであり、10未満F(4,10,2)は4を返すている1ビットの4-bitパターンの数（可能なパターンを列挙し、制限に対してテストし、有効なパターンを数えることは実用的ではありません。

この方法を効率的に行うための考え方はありますか？

Answer 1

これは宿題の質問としてタグ付けされているため、あなたのアイデアを提供してください。 は、効率の悪いアルゴリズムを常に設計し、それを分析して効率を試してみましょう。

Answer 2

制限の下の範囲を2^mの固定サイズの領域に分割し、プレフィックスを考慮してください。

Answer 3

ちょっとヒントですが、これを誘導的に/再帰的に（あなたが好むどんなモニカーでも）攻撃しようとします。自分自身の小さなインスタンスに問題を減らします。