文字列を数字に対応させたいというときは良くあります。
-
aaa-> $111$ -
aab-> $112$
といった感じに。
a~f を用いた $16$ 進数も、このような対応付けの一種と言えます。
-
10-> $16$ -
ff-> $15\times16+15=255$
いわゆる Excel 進数
ここで、次のような数え方を考えてみましょう。
- まず、
a~zまでを使う - それが終わったら、
aa~zzまでを使う - それが終わったら（以下略）
皆様にも馴染みの深い、Excel の列 です。
しかし、例えば、a~z の $26$ 文字を、$0\sim 25$ に割り当てた場合、以下のようになっておかしくなります。
-
a-> $0$ -
aa-> $0 \times 26+0=0$ - $25$ ->
z - $26$ ->
ba
a と aa が同じ数字になったり、z の次が ba になったりと、いろいろおかしいです。
これは、a を $0$ とみなしているにも関わらず、数え方がそうなっていないために起こります。
ならば、$0\sim26$ の $27$ 進数にすれば良いかというと、今度は別の問題が出てきます。便宜的に、「無」を _ と表現します。
- $0$ 番目の文字列 ->
__ - $1$ 番目の文字列 ->
_a - $26$ 番目の文字列 ->
_z - $27$ 番目の文字列 ->
a_ - $28$ 番目の文字列 ->
aa
本来、_z の次は aa であるべきですが、a_ になってしまいます。これでは、正しい数え上げができません。
このような特殊な数え方をする $N$ 進数について考えていきます。
基本の進数の数え上げ
まずは簡単な例として、普通の $N$ 進数から。
変換
単純な $16$ 進数で考えると、$n$ と文字列は以下の通りシンプルに変換できます。
- $10,000$ 番目の文字列は？
- $10,000$ を $16$ でわるとあまり $0$、よって $0$ 番目の文字である0（$1$ 桁目）
- $\lfloor\frac{10000}{16}\rfloor = 625$
- $625$ を $16$ でわるとあまり $1$、よって $1$ 番目の文字である1（$2$ 桁目）
- $\lfloor\frac{625}{16}\rfloor = 39$
- 同様に、7（$3$ 桁目）
- 同様に、2（$4$ 桁目）
- よって2710 -
2710は何番目の数？- $2\times16^3+7\times16^2+1\times16+0\times 1=10,000$
数え上げ表
また、「$D$ 桁以下の文字列が何個あるか」も非常に考えやすいです。$10$ 進数を考えます。これはほぼ自明に $10^D$ です（※ 0 もカウントすることに注意してください）。
$D$ 桁以下の文字列の個数がわかるということは、ちょうど $D$ 桁の個数も当然わかります。「ちょうど $D$ 桁になる文字列」の個数は、$10^D-10^{(D-1)}=9 \cdot 10^{(D-1)}$ です。
表にまとめるとこんな感じです。
$N$ 進数の数え上げ表（$10$ 進数の場合）
| 桁 | 範囲 | 個数 | 桁（累計） | 範囲 | 個数 |
|---|---|---|---|---|---|
| $D=0$ | $[0,1)$ | $1$ | $D\leq0$ | $[0,1)$ | $1$ |
| $D=1$ | $[1,10)$ | $9$ | $D\leq1$ | $[0,10)$ | $10$ |
| $D=2$ | $[10,100)$ | $90$ | $D\leq2$ | $[0,100)$ | $100$ |
| $D=3$ | $[100,1000)$ | $900$ | $D\leq3$ | $[0,1000)$ | $1000$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $D=M$ | $[10^{M-1},10^M)$ | $9 \times 10^{M-1}$ | $D\leq M$ | $[0,10^M)$ | $10^M$ |
※ $D=0$ のときは、$0$ 桁の文字列であり、つまり 0 がそれにあたります。
特殊な進数の数え上げ
では、Excel 進数などで使われる数え上げについて、同じようなパターンで検証しています。AA だとわかりづらいので、1~9 の $9$ 種類の数を使う文字列で、Excel の列のように増えていくものとします。
結論から言うと、以下のように、1-indexed の $9$ 進数として考えるとうまく変換できます。
- $19$ 番目の文字列は？
- $19$ を $9$ で割るとあまり $1$、よって、$1$ 番目の文字である1（$1$ 桁目）
- $(\lceil \frac{19}{9} \rceil-1) = 2$
- $2$ を $9$ で割るとあまり $2$、よって、$2$ 番目の文字である2（$2$ 桁目） -
21はどんな数？- こっちは普通に $N$ 進数として考えて大丈夫です
- $2\times9+1 = 19$
※ 1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,21 より（1-indexedの） $19$ 番目の文字列です
※ 文字列の変換について、プログラム上は、各桁ごとにデクリメントした上で 0-indexed と考える方が簡潔に実装できます（詳細は後述する実装例）
数え上げ表
こちらは、単純な $N$ 進数とは変わって、差分の法がわかりやすいです。ちょうど $D$ 桁に含まれる文字列は 1~9 を $D$ 個あてはめるだけなので、$9^D$ です。表にまとめます。
特殊 $N$ 進数の数え上げ表（$9$ 進数の場合）
| 桁 | 範囲 | 個数 | 桁（累計） | 範囲 | 個数 |
|---|---|---|---|---|---|
| $D=0$ | $[1,1)$ | $0$※ | $D\leq0$ | $[1,1)$ | $0$ |
| $D=1$ | $[1,11)$ | $9$ | $D\leq1$ | $[1,11)$ | $9$ |
| $D=2$ | $[11,111)$ | $81$ | $D\leq2$ | $[1,111)$ | $90$ |
| $D=3$ | $[111,1111)$ | $729$ | $D\leq3$ | $[1,1111)$ | $819$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $D=M$ | $[111\cdots,111\cdots)$ | $9^M$ | $D\leq M$ | $[1,111\cdots)$ | $\frac{9^{M+1}-1}{8}-1$ |
※ $D=0$ のときは例外処理が必要です。なんか数学的に気持ち悪いので、$[1,1)$ に $1$ 個の「無」の文字列が含まれると考えれば累計の $-1$ も消えてスッキリしますが、まあ、これは捉え方の問題で、やる計算は同じです。
名前
このような特殊な $N$ 進数に名前があるのかというと、当然あって、bijective numeration と呼ばれているらしいです。
bijective とは「全単射」のことであり、つまり一対一対応のことです。
どういうことかというと、まず、普通の $N$ 進数だと、1 も 01 も 001 も同じ数（$=1$）を示してしまいます。この点、bijective-N 進数だと、異なる文字列が同じ数を示すということがなく、一対一対応します。
さて、この bijective-N ですが、日本語で定まった訳がないようです。一応、参考記事 3では bijective numeration に対して「全単射記数法」という訳を当てています。ほぼ直訳ですが、まあ誰が訳してもこうなりそうですし、妥当だと思います。
という訳で、本記事では、この訳語を採用し定着させるとともに、他に「全単射 $N$ 進数」といった表記を提案したいと思います。
例）「Excel の列は、$26$ を基数とした全単射 $26$ 進数によって管理されている」
実装及び検証
数→文字列
文字列→数