木のナンバリング

それぞれの木に一意な番号をふります。

基本的には写像 f: N × N -> N を考えます。（数学的に言えば、自然数が自由マグマをなすような二項演算であればいい、となるんでしょうか（よくわからない））

方法

具体的には色々考えられます。現在は四角埋めに落ち着いていますが、とりあえず紹介しておきます。

f(x, y) = 2 ** x * (2 * y + 1)

インフレが激しいため不採用です。

x \ y	0	1	2	3	4
0	1	3	6	10	15
1	2	5	9	14
2	4	8	13
3	7	12
4	11

後述の四角埋めのほうが都合が良かったので廃止しました。

x \ y	0	1	2	3	4
0	1	4	9	16	25
1	2	3	8	15	24
2	5	6	7	14	23
3	10	11	12	13	22
4	17	18	19	20	21

現在採用している案です。特徴として番号順がそのまま高さ順になっているため、例えば木の高さによって品詞を決定すれば、

などの利点があることから採用しました。

x \ y	0	1	2	3	4
0	1	4	5	16	17
1	2	3	6	15	18
2	9	8	7	14	19
3	10	11	12	13	20
4	25	24	23	22	21

四角埋めに加わる特徴として、自然数の差が１である木同士の編集距離も１になっています。それによる利点が特に思いつかない割に計算が面倒なので、採用を見送っています。

x \ y	0	1	2	3
0	1	3	9	11
1	2	4	10	12
2	5	7	13	15
3	6	8	14	16
4	17

Yuki さんの提案によるものです。

ビット演算で高速に処理ができることが利点です。

文法を考えるにあたって四角埋めの性質が面白そうなのでZ階数曲線の採用は見送っていますが、Z階数曲線にも文法に利用できそうな性質があったら採用するかもしれません。