概要
- ある記号(の集合)から生成可能な文字列と自然数との全単射を構成したい
- 有名なゲーデル数によるコード化は全射ではない
- 中国の剰余定理に根ざしたβ関数のほうも全射ではなかったはず
- 文字列に$ｂ$進数表現を対応させる方法では，この問題はうまくいかない
- 辞書式順序で$１$個ずつ直接数え上げるような方法はしたくない
定義
-
$\Sigma$：（文字列に利用できる）記号の有限集合
- $e.g. \Sigma=\{a,b,c\}$
-
$\Sigma^{+}$：$\{\alpha_1\alpha_2...\alpha_n \mid \alpha_1,...,\alpha_n \in \Sigma, n \geq 1 \}$($\Sigma$からなる$1$文字以上の文字列全体)
- $e.g. \{a,b,c\}^{+} = \{a,b,c,aa,ab,ac,ba,...\}$
-
$|\Sigma|$：$\Sigma$の要素数
- $e.g. |\{a,b,c\}| = 3$
- 文脈で判断可能な場合，$ｂ=|\Sigma|$ のこととする
-
$|w|$ ($w \in \Sigma^{+}$)：文字列$w$の長さ
- $e.g. |aabbcc| = 6$
-
$\mathbb{N}$：自然数全体
素朴な考え方
1.はうまくいかない(下で解説)．
2.はうまくいくけど，もう少し効率的にできたら嬉しい．
数え上げる方法だと，自身の文字列が$i$番目に現れるまで，$i$以下の文字列すべてに対し自身と一致するかを確認しなければならないので
実験
$\Sigma = \{a,b,c\}$ とする
(素朴に3進数に対応付ける場合：$a:"0", \ \ b:"1", \ \ c:"2"$)
| $w \in \{a,b,c\}^+$ | $n \in \mathbb{N}$ | $n$の$3$進数表現 |
|---|---|---|
| $a$ | $０$ | "0" |
| $b$ | $１$ | "1" |
| $c$ | $2$ | "2" |
| $aa$ | $3$ | "10" |
| $ab$ | $4$ | "11" |
| $ac$ | $5$ | "12" |
| $ba$ | $6$ | "20" |
- $ｋ(ｋ \geq 2)$桁で表現される範囲が通常の$ｂ$進数表記と異なる
- 普通の表記では，$ｂ$進数$ｋ$桁で表現される値の種類は，$ｂ^{ｋ}-ｂ^{ｋ-1}$
- $e.g.$ $10$進数で$2$桁：10〜99 までの $10^{2}-10^{1}=90$
- ところがこの対応だと，$3^2-3=6$ だが， $aa〜cc$ は$9$通りの表現
- これがややこしくしている原因なのでは？（予想）
→ この予想というか伏線はあとで回収されることに...!
- 普通の表記では，$ｂ$進数$ｋ$桁で表現される値の種類は，$ｂ^{ｋ}-ｂ^{ｋ-1}$
- $2$文字以上のときに，先頭文字$a$を$1$としてみなす方法もだめ（$aaa$は$9$ではなく$12$が対応します）
問題を解く
考え方
- 全単射なので逆写像が存在するため，まず，$\mathbb{N}\to\Sigma^+$を数え上げずに構成する方法を考察
- $1$桁までは，素朴に$ｂ$進数として考えれば良さそう
- $ｋ (ｋ\geq 2)$桁では，既に求まった文字列に$1$文字追加することで，すべての長さのすべてのバリエーションの文字列を対応できそう
- 参考１：トランプを用いるプログラミングの例
- $0〜51$までの自然数をトランプに割り当てる方法：$13$で割った商（$0〜3$）を♠〜♥に，余り（$0〜12$）を$1〜13$に割り当てる
- ２次元配列を使わずに，このように１次元でデータ管理するほうが便利なことが，静的なゲーム（囲碁や将棋，オークのカードゲーム等）には多いらしい...
- 参考２：ハフマン符号を求める（再帰的な）アルゴリズム
- より簡単な条件で求まった解(文字列)に，現在の文字をつなげることで解を求める(詳しくは，参考文献にあげた応用論理に載ってます)
- 参考１：トランプを用いるプログラミングの例
- (お気持ち)トランプの例に習って，現在の文字を$ｂ$で割った余りに対応する$ｂ$進文字とし，ハフマン符号を求めるアルゴリズムに習って，過去の解（$ｂ$で割った商に対応する文字列）に現在の文字をつなげれば良い
- ただこれって，$ｂ$進数になおす考えそのまま（うまくいかない）
- 表から，$(n/b)$-1番目の解に文字をつなげればうまく対応とれることがわかる
- 逆関数である，$\Sigma^+ \to \mathbb{N}$は上記の逆の操作をしてあげればよい
コード
haskellでコード書いてみた
- Ss：$\Sigma^+$ （Sigma starのつもりだったけど，今回はSpにすべきだった...まぁいいや)
- nToSs：$\mathbb{N} \to \Sigma^{+}$
- 👆はfoldの表現に直そうとしたらなんかややこしくなったので再帰のまま(fold使う良い記述があればおしえてください)
- ssToN：$\Sigma^+ \to \mathbb{N}$
data S = A | B | C deriving (Show, Enum, Bounded)
type Ss = [S]
base :: Int
base = succ $ fromEnum (maxBound :: S)
nToSs :: Int -> Ss
nToSs n
| a == 0 = s
| otherwise = nToSs (pred a) ++ s
where (a,r) = divMod n base
s = [toEnum r :: S]
ssToN :: Ss -> Int
ssToN = foldl (\x y -> succ x * base + fromEnum y) $ pred 0
{- Recursive ver.
ssToN [s] = fromEnum s
ssToN xs = succ (ssToN $ init xs) * base + (fromEnum $ last xs)
-}
検証
*Main> map nToSs [0..12]
[[A],[B],[C],[A,A],[A,B],[A,C],[B,A],[B,B],[B,C],[C,A],[C,B],[C,C],[A,A,A]]
*Main> map ssToN [[A],[B],[C],[A,A],[A,B],[A,C],[B,A],[B,B],[B,C],[C,A],[C,B],[C,C],[A,A,A]]
[0,1,2,3,4,5,6,7,8,9,10,11,12]
よさそう
発展（長さをもとめる）
追記：辞書式順序で利用する|Σ|分木に対して，その文字列が現れる位置を考えれば↓みたいな考察不要やんけ．．．
- |nToSs($m$)|を求めたい
- 普通の$ｂ$進表現文字列であれば，$^※μx(m \leq ｂ^x-1)$ で文字列の長さを求められる
$※μ$ は μ作用素（述語を満たす最小値を返す） - 今回も，$| w| \ ( w \in \Sigma^+)$ の大きさが値(自然数)の大きさに比例することにかわりないので，$μx(m \leq g(x)-1)$ という構造は同じ
- 普通の$ｂ$進表現文字列だと，$g(x) = ｂ^x$ということ
- ただし，$g(0) = 0$
- 今回の問題に対応する$g$は，上のコード(ssToN)より，$a_{n+1} = ｂ(a_n+1)$ の一般項$a_n$
- $a_1=ｂ$の特殊解がある漸化式と思えば，高校数学
- 上の漸化式を機械的に解くと，$g(ｘ)=ｂ\frac{ｂ^{x}-1}{ｂ-1}$
- これは，初項$ｂ$公比$ｂ$の等比数列の和である
- 要は，$ｋ$桁表現においては，$ｂ^ｋ$個の表現（だけ）でなく$ｂ^ｋ+ｂ^{ｋ-1}+...+ｂ$の表現ができるよということ
- これって，今回の文字列が接頭に$0$を許す$ｂ$進数表現だと考えれば当たり前だ（だから，上の方では通常の$ｂ$進数表記と記しました）
- $e.g.$ $ｂ=10,ｋ=2$だと，通常の10〜99 に 00〜09 までの表現が加わる...
- → 伏線回収(ちょっと変わった進法だともみなせるかも)
まとめ
- 文字列と自然数の全単射問題の難しさは，自然数$n$に対応する$ｂ$進数表現文字列が一意でないことが原因っぽい（10を010としても，0010としても正しい）
- そこで，再帰的なアルゴリズムを用いて，接頭文字列に0...0（に対応する記号）が来るパターンの文字列も数え上げることができた
- 機械的に説いた数式（今回の場合，漸化式から得られた一般項）から認識を拡張できるから数学楽しい
参考文献
[1] 有川節夫（監修），西野哲朗，石坂裕毅，形式言語の理論 第2刷，丸善，1999：$\Sigma$の定義や，文字列に関する基本的な話はこの本を参考にした．
[2] 桔梗宏孝，応用論理 (情報数学講座【1巻】) 初版1刷，共立出版，1996：ハフマン符号を求めるアルゴリズムは，この本で勉強しました(現在Wikipediaにある解説よりずっとわかりやすい)．再帰的なプログラミングに関する話題が豊富で，解説も秀逸です．
余談
- 何故この記事を書いたか？
- 以下の検索ワードでQiitaの記事，およびGoogle先生に問い合わせたけど，少なくとも上位に今回求こめる話がヒットしなかったので
「文字列 自然数 対応」「文字列 数え上げ」「文字列 進数」
→ 求める話はヒットしなかったけど，学生時代一緒にバンド組んでた友人の論文がヒットして草ｗ - プログラミング詳しい人でも，この問題の解法がパッと思いつかない人がいたので（みんなやはり$ｂ$進数でいけると思うみたい）その意味でも書く意義があると判断
- 本記事の内容はどこで役立つの？
- アプリ作成等の現場ではあまりないかもしれない...
- ただし，一般に文字列を自然数と対応付けるという問題はよくあり，数え上げるよりも直接的に文字列や値を求める方法があることが嬉しいことはありそう．
- 私が考察して満足できたからいいんですよ...