0

f_k(n)よりも小さいすべての整数を生成し2^k、設定されたビット数で並べ替え、次に値で並べ替える生成関数は何ですか?

の期待される出力k = 4:

f_4( 0) = b0000 =  0
--------------------
f_4( 1) = b0001 =  1
f_4( 2) = b0010 =  2
f_4( 3) = b0100 =  4
f_4( 4) = b1000 =  8
--------------------
f_4( 5) = b0011 =  3
f_4( 6) = b0101 =  5
f_4( 7) = b0110 =  6
f_4( 8) = b1001 =  9
f_4( 9) = b1010 = 10
f_4(10) = b1100 = 12
--------------------
f_4(11) = b0111 =  7
f_4(12) = b1011 = 11
f_4(13) = b1101 = 13
f_4(14) = b1110 = 14
--------------------
f_4(15) = b1111 = 15

二項係数は、ビットが設定されたC(k,x)整数がいくつ存在するかを予測するという観測を行いました。x

C(4,0) = 1
C(4,1) = 4
C(4,2) = 6
C(4,3) = 4
C(4,4) = 1

ビットが設定されたすべての整数xを生成する方法も見つけました。

これに基づいて、私は解決策を考え出しました。

int f(int k, int n) {
    int x = 0;
    int c = binomial(k, x);
    while (n >= c) {
        n -= c;
        ++x;
        c = binomial(k, x);
    }

    int v = (1 << x) - 1;  // v is exactly x many one bits
    for (int i = 0; i != n; ++i) {
        // next integer with x bits set
        int t = (v | (v - 1)) + 1;
        v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
    }

    return v;
}

whileただし、特にループを考慮すると、私の解決策は非効率的だと思います。これには、ビットマジックを含む、はるかに最適化されたソリューションがあると直感的に感じています。

関数を見つけるためのボーナスポイントは、リスト内の次/前の要素を返し、前/次の要素が与えられます。

4

1 に答える 1