1

0<=r<=n の時点で選択された n 個の要素のすべての可能な組み合わせを計算する必要があります。そのための 1 つの方法は、0 から 2^n-1 までの数値を生成することです。しかし、その数値に設定されたビット数に基づいて数値がソートされるように、これらの数値を生成する必要があります。n=3 の場合:

0         // numbers with 0 bits set

1 2 4     // numbers with 1 bits set

3 5 6     // numbers with 2 bits set

7         // numbers with 3 bits set

ビットセットの昇順/降順でソートされるように数値を生成する方法を知る必要がありますか?

4

5 に答える 5

0

再帰的に行うことができます：

void setnbits(unsigned int cur, int n, int toset, int max)
{
    if(toset == 0)
    {
        printf("%d ", cur >> (n + 32 - max) , n);
        return;
    }
    toset--;
    for(int i = 1 ; i <= n-toset ; i++)
    {
        setnbits((cur >> i) | 0x80000000, n-i, toset , max);
    }
}

次のように呼び出すことができます。

for(int z = 0 ; z < 4 ; z++)
{
    printf("%d bits: ", z);
    setnbits(0, 3, z, 3);
    printf("\n");
}

プリント:

0 bits: 0
1 bits: 1 2 4
2 bits: 3 5 6
3 bits: 7

番号は番号順であるとは限りません。

于 2013-01-28T13:38:48.423 に答える
0

以下は、数値表現で設定されたビット数をカウントする簡単な方法関数です。

// Counts how many bits are set in the representation of the input number n
int numOfBitsSet(int n)
{
    int cnt = 0;
    while (n != 0)
    {
        cnt += (n & 1);
        n = n >> 1;
    }

    return cnt;
}

そして、あなたが望むことをする（C++ 11）プログラムでそれを使用する方法は次のとおりです。

#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

using namespace std;

int main()
{
    // For instance...
    int n = 3;

    // Fill up a vector of 2^n entries (0 .. 2^(n - 1))
    vector<int> v(1 << n);
    iota(begin(v), end(v), 0);

    // For each number of bits...
    for (size_t i = 0; i <= n; i++)
    {
        cout << "Numbers with " << i << " bits set: ";

        // Find the first number with i bits set...
        auto it = find_if(begin(v), end(v), [i] (int x) { 
            return (numOfBitsSet(x) == i); 
            });

        while (it != end(v))
        {
            cout << *it << " ";

            // Find the next number with i bits set...
            it = find_if(next(it), end(v), [i] (int x) { 
                return (numOfBitsSet(x) == i); 
                });
        }

        cout << endl;
    }
}

C++11 を使用できない場合は、ラムダの代わりにファンクターを使用std::iotaし、手動ループに置き換える必要があります。

#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

using namespace std;

struct bit_count_filter
{
    bit_count_filter(int i) : _i(i) { }
    bool operator () (int x) const { return numOfBitsSet(x) == _i; }
    int _i;
};

int main()
{
    // For instance...
    int n = 3;

    // Fill up a vector of 2^n entries (0 .. 2^(n - 1))
    vector<int> v(1 << n);
    for (size_t i = 0; i < v.size(); i++)
    {
        v[i] = i;
    }

    // For each number of bits...
    for (size_t i = 0; i <= n; i++)
    {
        cout << "Numbers with " << i << " bits set: ";

        // Find the first number with i bits set...
        auto it = find_if(begin(v), end(v), bit_count_filter(i));
        while (it != end(v))
        {
            cout << *it << " ";

            // Find the next number with i bits set...
            it = find_if(next(it), end(v), bit_count_filter(i));
        }

        cout << endl;
    }
}
于 2013-01-28T13:07:08.157 に答える
0

それはとても簡単です。次の 2 つのケースがあります。

1) 最後の 1 ビットの前に 0 ビットがあります: 00011100100 1 -> 0001110010 1 0.

左に動かせばいいだけ

2) 1 ビットのチェーンがあります: 00011 01111 00 -> 00011 1 000 111

次に、最後の 1 ビットを左側 (チェーンの前) の最も近い 0 ビットに移動し、そのチェーンの他のすべてのビットを右側に移動する必要があります。

このようにして、必要なすべての数値を昇順で取得します。

于 2013-03-02T18:59:16.353 に答える
0

いくつかのアイテムのすべての組み合わせを反復処理することは、quant_dev hereによって適切にカバーされています。

于 2013-01-28T12:49:09.193 に答える
0

組み合わせを生成する通常のアルゴリズムを実装しますが、1 ビット セットに従って並べ替えられた数値を格納する追加の配列も保持します。次に、生成された組み合わせごとに、前述のように並べ替えられた配列の対応する位置にある数字から 1 を引いた数字に置き換えます。

于 2013-01-28T12:54:14.783 に答える