分類と序数

まず、数値 $x$ を固定桁数（ビット幅 $w$）の２進数にして、「1」の個数 $b$ で分類します。

すると、分類ごとに、２進数の一覧ができます。

次に、２進数の一覧は、昇順で並べるようにします。

結果、「 $n$：一覧での番号（序数）」と「 $x$：２進数の値」の対 $\{n,x\}$ を作ることができます。

「1」の個数で分類

ビット幅 $w$ のデータ $x$ から、各ビットの "1" を数えて

　　1 が 0 個：$b=0$
　　1 が 1 個：$b=1$
　　...
　　1 が w 個：$b=w$

として、$(w+1)$ 種類に分類します。

$b$ は、プログラムでは

　　$b = bitcount \left( x \right)$

などですが、数式にすると

　　$bit \left( d, k \right) = \lfloor 2^{-k} d \rfloor \ mod\ 2$
　　$b = \sum_{k=0}^{w-1}{bit \left( x, k \right)}$

こんな感じ？

各ビットの "1" を数える関数 $bitcount \left( x \right)$ の例

bitcount関数

int bitcount(unsigned int x) {
    int b = 0;
    while (x != 0) {
        b += (x & 1);
        x >>= 1;
    }
    return b;
}

x86/64 の POPCNT 命令が使えれば、１命令なのに...

序数 n

分類 $\left( w,b \right)$ での一覧にて、２進数の値 $x$ に序数 $n$ を 0 から割り当てます。

具体例がわかりやすいので、例示します。

$w=1$ の場合

$n$ ＼ $b$	0	1
0	0	1
計	1	1

$w=2$ の場合

$n$ ＼ $b$	0	1	2
0	00	01	11
1		10
計	1	2	1

$w=3$ の場合

$n$ ＼ $b$	0	1	2	3
0	000	001	011	111
1		010	101
2		100	110
計	1	3	3	1

$w=4$ の場合

$n$ ＼ $b$	0	1	2	3	4
0	0000	0001	0011	0111	1111
1		0010	0101	1011
2		0100	0110	1101
3		1000	1001	1110
4			1010
5			1100
計	1	4	6	4	1

分類 $\left( w,b \right)$ に含まれる「計：値の個数 $l$」は、二項係数

　　$l = C(w,b) = \frac{w!}{b!(w-b)!}$

になっています。

二項係数の参照表

二項係数は、パスカルの三角形

					1
				1		1
			1		2		1
		1		3		3		1
	1		4		6		4		1
1		5		10		10		5		1

を左詰にして、参照表 $C(w,b)$

w ＼ b	0	1	2	3	4	5
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
...

を作ります。これで階乗の計算が不要になります。

データ x と序数 n の変換

ビット幅 $w$ と分類 $b$ を共通項として

データ $x$ から序数 $n$ を得る
序数 $n$ からデータ $x$ を得る

を考えます。

データ x から序数 n を得る

処理内容

データ $x$ の最上位ビットから、各ビットに対する 変則重み の和で求めます。

初期状態は
　　序列　　： $n' = 0$
　　ビット幅： $w' = w$
　　$1$ の個数： $b' = b$
とします。

$n',w',b'$ は変数です。

処理は、最大 $\left( w-1 \right)$ 回のループになります。

ループの中身は
　　$bit(x, w'-1) \ne 0$
の場合は
　　$n'$ に $C \left( w'-1,\ b' \right)$ を加える
　　$b'$ を $1$ 減らす
を実行します。

$w'$ のデクリメントがあります。

ループの終了条件は
　　$b' = 0$
または
　　$b' = w'$
です。

$0$ 回ループもあり得ます。

例： w=4, b=2 の場合

初期状態は

$x$	$b'$	$n'$
0011	$2$	$0$
0101	$2$	$0$
0110	$2$	$0$
1001	$2$	$0$
1010	$2$	$0$
1100	$2$	$0$

　　$w' = 4$

です。最初のループで

$x_3$	$x_{210}$	$b'$	$n'$	$n'$
0	011	$2$	$0$	$0$
0	101	$2$	$0$	$0$
0	110	$2$	$0$	$0$
1	001	$1$	$3$	$C \left( 3,2 \right)$
1	010	$1$	$3$	$C \left( 3,2 \right)$
1	100	$1$	$3$	$C \left( 3,2 \right)$

　　$w' = 3$

に更新されます。次のループでは

$x_3$	$x_2$	$x_{10}$	$b'$	$n'$	$n'$
0	0	11	$2$	$0 = 0 + 0$	$0 + 0$	終
0	1	01	$1$	$1 = 0 + 1$	$0 + C \left( 2,2 \right)$
0	1	10	$1$	$1 = 0 + 1$	$0 + C \left( 2,2 \right)$
1	0	01	$1$	$3 = 3 + 0$	$C \left( 3,2 \right) + 0$
1	0	10	$1$	$3 = 3 + 0$	$C \left( 3,2 \right) + 0$
1	1	00	$0$	$5 = 3 + 2$	$C \left( 3,2 \right) + C \left( 2,1 \right)$	終

　　$w' = 2$

に更新されます。$n'$ が $0$ か $5$ の場合では、ここで終了です。次が最後のループで

$x_3$	$x_2$	$x_1$	$x_0$	$b'$	$n'$	$n'$
0	0	$_1$	$_1$	$_2$	$0 = 0 + 0$	$0 + 0$
0	1	0	$_1$	$1$	$1 = 0 + 1 + 0$	$0 + C \left( 2,2 \right) + 0$
0	1	1	$_0$	$0$	$2 = 0 + 1 + 1$	$0 + C \left( 2,2 \right) + C \left( 1,1 \right)$
1	0	0	$_1$	$1$	$3 = 3 + 0 + 0$	$C \left( 3,2 \right) + 0 + 0$
1	0	1	$_0$	$0$	$4 = 3 + 0 + 1$	$C \left( 3,2 \right) + 0 + C \left( 1,1 \right)$
1	1	$_0$	$_0$	$_0$	$5 = 3 + 2$	$C \left( 3,2 \right) + C \left( 2,1 \right)$

　　$w' = 1$

に更新されて、$n=n'$ が得られます。

序数 n からデータ x を得る

データ $x$ に対応する最上位ビットから、各ビットに対する 変則重み を使って、$x$ の各ビットを求めます。

初期状態は
　　データ　： $x' = 0$
　　序列　　： $n' = n$
　　ビット幅： $w' = w$
　　$1$ の個数： $b' = b$
とします。

$x',n',w',b'$ は変数です。

処理は、最大 $\left( w-1 \right)$ 回のループになります。

ループの中身は
　　$n' \ge C(w'-1,b')$
の場合に
　　$n'$ から $C \left( w'-1,\ b' \right)$ を引く
　　$b'$ を $1$ 減らす
　　$x'$ に $2^{w'-1}$ を加える
を実行します。

$w'$ のデクリメントがあります。

ループの終了条件は
　　$b' = 0$
または
　　$b' = w'$
です。$0$ 回ループもあり得ます。

最後に $b'$ の残り追加
　　$x'$ に $2^{b'}-1$ を加える
で完了です。

「データ x から序数 n を得る」に対して、「各ビット」と「対応する二項係数」を入れ替えた処理になります。

例： w=4, b=2 の場合

初期状態は

$n$	$n'$	$b'$
0	0	2
1	1	2
2	2	2
3	3	2
4	4	2
5	5	2

　　$w' = 4$

です。最初のループで

$n$	$n'$	$b'$	$x'_3$	$n'$ の更新
0	0	2	0	$0$
1	1	2	0	$0$
2	2	2	0	$0$
3	0	1	1	$C\left( 3,2 \right) = 3$
4	1	1	1	$C\left( 3,2 \right) = 3$
5	2	1	1	$C\left( 3,2 \right) = 3$

　　$w' = 3$

に更新されます。次のループでは

$n$	$n'$	$b'$	$x'_3$	$x'_2$	$n'$ の更新
0	0	2	0	0	$0$	終
1	0	1	0	1	$C\left( 2,2 \right) = 1$
2	1	1	0	1	$C\left( 2,2 \right) = 1$
3	0	1	1	0	$0$
4	1	1	1	0	$0$
5	0	0	1	1	$C\left( 2,1 \right) = 2$	終

　　$w' = 2$

に更新されます。$n$ が $0,5$ の場合では、ここでループ終了条件に合致します。次が最後のループで

$n$	$n'$	$b'$	$x'_3$	$x'_2$	$x'_1$	$n'$ の更新
0	0	2	0	0	0	$0$
1	0	0	0	0	1	$C\left( 1,1 \right) = 1$
2	1	1	0	1	0	$0$
3	0	1	1	0	0	$0$
4	0	0	1	0	1	$C\left( 1,1 \right) = 1$
5	0	0	1	1	0	$0$

　　$w' = 1$

に更新されます。ループを抜けると、$b'$ のビット数で $x'$ を更新して

$n$	$n'$	$b'$	$x'_3$	$x'_2$	$x'_1$	$x'_0$	$x'$ の更新
0	0	2	0	0	1	1	11
1	0	0	0	0	1	0	00
2	1	1	0	1	0	1	01
3	0	1	1	0	0	1	01
4	0	0	1	0	1	0	00
5	0	0	1	1	0	0	00

となって、$x=x'$ が得られます。

サンプルプログラム

sample.c

#include <stdio.h>
#include <stdlib.h>

static unsigned int **wbtab = NULL; /* 二項係数の参照用テーブル */

/* 二項係数のテーブルを用意する */
void make_wbtab(unsigned int w) {
    unsigned int i, j;
    if (wbtab != NULL)
        return;
    wbtab = (unsigned int **) malloc((w+1) * sizeof(unsigned int *));
    for (i = 0; i <= w; i++)
        wbtab[i] = (unsigned int *) malloc((i+1) * sizeof(unsigned int));
    wbtab[0][0] = 1;
    for (i = 1; i <= w; i++) {
        wbtab[i][0] = 1;
        for (j = 1; j < i; j++)
            wbtab[i][j] = wbtab[i-1][j-1] + wbtab[i-1][j];
        wbtab[i][i] = 1;
    }
}

/* 二項係数 C(w,b) をテーブル参照で得る */
unsigned int comb(unsigned int w, unsigned int b) {
    return wbtab[w][b];
}

/* 各ビットの "1" を数える */
int bitcount(unsigned int x) {
    int b = 0;
    while (x != 0) {
        b += (x & 1);
        x >>= 1;
    }
    return b;
}

/* データ x から序数 n を得る */
unsigned int wb_x2n(unsigned int w, unsigned int b, unsigned int x) {
    unsigned int n = 0;
    while (b && b < w) {
        w -= 1;
        if ((x & (1 << w)) != 0) {
            n += comb(w, b); /* C(w,b) */
            b -= 1;
        }
    }
    return n;
}

/* 序数 n からデータ x を得る */
unsigned int wb_n2x(unsigned int w, unsigned int b, unsigned int n) {
    unsigned int x = 0, c;
    unsigned int m = 1 << (w - 1);
    while (b && b < w) {
        w -= 1;
        c = comb(w, b); /* C(w,b) */
        if (n >= c) {
            x |= m;
            n -= c;
            b -= 1;
        }
        m >>= 1;
    }
    x |= (1 << b) - 1;
    return x;
}

/*
 * テスト用
 */

/* 分類を変更せず、次のデータへ */
static unsigned int wb_next(unsigned int x) {
    unsigned int m, n, o;
    m = x & (-x);  /* 処理の開始位置を求める */
    o = 1;
    for (;;) {
        n = m << 1;
        if ((x & n) == 0)
            return (x ^ m ^ n);
        x ^= (m ^ o);
        m <<= 1;
        o <<= 1;
    }
}

/* ２進数での出力 */
static void print_bin(unsigned int w, unsigned int x) {
    unsigned int k = w;
    while (k-- != 0)
        putchar('0' + ((x >> k) & 1));
}

/* 分類(w,b) の一覧出力 */
static void print_wb(unsigned int w, unsigned int b) {
    unsigned int m, n;
    unsigned int p, x;
    m = (1 << w) - 1;
    x = (1 << b) - 1;
    n = 0;
    do {
        printf("%3d: ", n++);
        print_bin(w, x);
        printf("\n");
        p = x;
        x = wb_next(p) & m;
    } while (p < x);
}

/* ビット幅 w での全体出力 */
void print_w(unsigned int w) {
    unsigned int b;
    for (b = 0; b <= w; b++) {
        printf("%d,%d ------\n", w, b);
        print_wb(w, b);
    }
}

/* make_wbtab(w) の確認用 */
void print_wbtab(unsigned int w) {
    unsigned int i,j;
    make_wbtab(w);
    for (i = 0; i <= w; i++) {
        printf("%2d:", i);
        for (j = 0; j <= i; j++)
            printf(" %2d", comb(i, j));
        printf("\n");
    }
}

/* wb_x2n の動作確認用 */
void print_wb_x2n(unsigned int w, unsigned int b) {
    unsigned int n, x;
    unsigned int i, wbn;

    make_wbtab(w);
    wbn = comb(w, b);
    x = (1 << b) - 1;
    for (i = 0; i < wbn; i++) {
        n = wb_x2n(w, b, x);
        printf("%2d: %2d <- ", i, n);
        print_bin(w, x);
        printf("\n");
        x = wb_next(x);
    }
}

/* wb_n2x の動作確認用 */
void print_wb_n2x(unsigned int w, unsigned int b) {
    unsigned int n, x, xx;
    unsigned int wbn;

    make_wbtab(w);
    wbn = comb(w, b);
    x = (1 << b) - 1;
    for (n = 0; n < wbn; n++) {
        xx = wb_n2x(w, b, n);
        print_bin(w, x);
        printf(": ");
        print_bin(w, xx);
        printf(" <- %2d\n", n);
        x = wb_next(x);
    }
}

print_w(4)の実行結果：分類(4,b)の一覧

4,0 ------
  0: 0000
4,1 ------
  0: 0001
  1: 0010
  2: 0100
  3: 1000
4,2 ------
  0: 0011
  1: 0101
  2: 0110
  3: 1001
  4: 1010
  5: 1100
4,3 ------
  0: 0111
  1: 1011
  2: 1101
  3: 1110
4,4 ------
  0: 1111

print_wbtab(4)の実行結果：二項係数の参照表

 0:  1
 1:  1  1
 2:  1  2  1
 3:  1  3  3  1
 4:  1  4  6  4  1

print_wb_x2n(4,2)の実行結果：データxから序数nを得る

 0:  0 <- 0011
 1:  1 <- 0101
 2:  2 <- 0110
 3:  3 <- 1001
 4:  4 <- 1010
 5:  5 <- 1100

print_wb_n2x(4,2)の実行結果：序数nからデータxを得る

0011: 0011 <-  0
0101: 0101 <-  1
0110: 0110 <-  2
1001: 1001 <-  3
1010: 1010 <-  4
1100: 1100 <-  5

「圧縮されたデータは偏っているので再圧縮できそう」では、この変換を応用して、使用する数値の範囲を絞る方法を試していました。 $w$ は $4096$ より大きい値を試しています。

※ $x$ と $n$ を直接変換するテーブルを用いると、$x$ と $n$ の変換は高速化できます。しかし、ビット幅 $w$ が $30$ 程度より大きくなると、個人 PC では RAM 容量の問題が発生します。