0と1の組み合わせ表現一覧の順番と数値

# 分類と序数

まず、数値 $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)}$

こんな感じ？

<details><summary>各ビットの "1" を数える関数 $bitcount \left( x \right)$ の例</summary><div>

```c:bitcount関数
int bitcount(unsigned int x) {
    int b = 0;
    while (x != 0) {
        b += (x & 1);
        x >>= 1;
    }
    return b;
}
```

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

</div></details>

## 序数 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)!}$

になっています。

<details><summary>二項係数の参照表</summary><div>

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

|   |   |   |   |    | 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 |
| **...** | | | | | | |

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

</div></details>

# データ 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'$ | | $x'$ |
|:-:|:-:|:-:|:-:|:----:|
| 0 | 0 | 2 |   | 0000 |
| 1 | 1 | 2 |   | 0000 |
| 2 | 2 | 2 |   | 0000 |
| 3 | 3 | 2 |   | 0000 |
| 4 | 4 | 2 |   | 0000 |
| 5 | 5 | 2 |   | 0000 |

　　$w' = 4$

です。最初のループで

| $n$ | $n'$ | $b'$ | | $x'_3$ | $x'_{210}$ | $n'$ の更新 |
|:-:|:-:|:-:|:-:|:-:|:---:|:--------------------------|
| 0 | 0 | 2 |   | 0 | 000 | $0$                       |
| 1 | 1 | 2 |   | 0 | 000 | $0$                       |
| 2 | 2 | 2 |   | 0 | 000 | $0$                       |
| 3 | 0 | 1 |   | 1 | 000 | $C\left( 3,2 \right) = 3$ |
| 4 | 1 | 1 |   | 1 | 000 | $C\left( 3,2 \right) = 3$ |
| 5 | 2 | 1 |   | 1 | 000 | $C\left( 3,2 \right) = 3$ |

　　$w' = 3$

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

| $n$ | $n'$ | $b'$ | | $x'_3$ | $x'_2$ | $x'_{10}$ | $n'$ の更新 | |
|:-:|:-:|:-:|:-:|:-:|:-:|:--:|:--------------------------|:-:|
| 0 | 0 | 2 |   | 0 | 0 | 00 | $0$                       | 終 |
| 1 | 0 | 1 |   | 0 | 1 | 00 | $C\left( 2,2 \right) = 1$ |    |
| 2 | 1 | 1 |   | 0 | 1 | 00 | $C\left( 2,2 \right) = 1$ |    |
| 3 | 0 | 1 |   | 1 | 0 | 00 | $0$                       |    |
| 4 | 1 | 1 |   | 1 | 0 | 00 | $0$                       |    |
| 5 | 0 | 0 |   | 1 | 1 | 00 | $C\left( 2,1 \right) = 2$ | 終 |

　　$w' = 2$

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

| $n$ | $n'$ | $b'$ | | $x'_3$ | $x'_2$ | $x'_1$ | $x'_0$ | $n'$ の更新 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:--------------------------|
| 0 | 0 | 2 |   | 0 | 0 | 0 | 0 | $0$                       |
| 1 | 0 | 0 |   | 0 | 0 | 1 | 0 | $C\left( 1,1 \right) = 1$ |
| 2 | 1 | 1 |   | 0 | 1 | 0 | 0 | $0$                       |
| 3 | 0 | 1 |   | 1 | 0 | 0 | 0 | $0$                       |
| 4 | 0 | 0 |   | 1 | 0 | 1 | 0 | $C\left( 1,1 \right) = 1$ |
| 5 | 0 | 0 |   | 1 | 1 | 0 | 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'$ が得られます。


# サンプルプログラム

```c: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);
    }
}
```

```console: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
```

```console:print_wbtab(4)の実行結果：二項係数の参照表
 0:  1
 1:  1  1
 2:  1  2  1
 3:  1  3  3  1
 4:  1  4  6  4  1
```

```console: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
```

```console: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
```

「[圧縮されたデータは偏っているので再圧縮できそう](https://qiita.com/ikiuo/items/d4dba8bdcecd13bae3ab)」では、この変換を応用して、使用する数値の範囲を絞る方法を試していました。 $w$ は $4096$ より大きい値を試しています。

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