レーマー符号

数学とくに組合せ数学において、レーマー符号（レーマーふごう、英: Lehmer code）は、n 個の数のすべての置換を符号化する方法の一つである。レーマー符号という名前はデリック・ヘンリー・レーマー（英語版）に由来するが、この符号は少なくとも1888年には知られていた^[1]^[2]。

符号

レーマー符号は、n 個の数の置換が

n!=n\times (n-1)\times \cdots \times 2\times 1

個存在するという事実を利用している。置換 σ は 1, …, n の像の列 (σ₁, …, σ_n) によって表すなら、n 個の数の並びによって符号化されることになる。しかし、こうした並びには置換を表さないもの（同じ数を二度使ったもの）も含まれている。ここで考察する符号は、先頭の数を n 個の数から選び、次の数は $n - 1$ 個の数から選び、そうしていって、最後の数はたった1個の数から選んでできるものである。

レーマー符号は、次の列である。

L(\sigma )=(L(\sigma )_{1},\ldots ,L(\sigma )_{n})\quad {\text{where}}\quad L(\sigma )_{i}=\#\{j>i:\sigma _{j}<\sigma _{i}\}

記号 L(σ)_i は、σ_i+1, …, σ_n のうち σ_i より小さいものの個数である。

$i < j$ かつ $σ i > σ j$ である添字の組 $i < j$ を σ の逆転と呼び、L(σ)_iは、逆転(i,j)がいくつあるかを表す（iは固定しiを変化させる）。このことから $L (σ) 1 + L (σ) 2 + \dots + L (σ) n$ は σ に逆転がいくつ現れるかを表していることが分かる。これは、恒等順列に変換するために必要な隣接互換の数と等しい。位置 iの値が0であればそこから右での最小であり（すなわち $σ i$ はその右にあるどの $σ j$ よりも小さい）、位置 iでの値 $n - i$ はそこから右での最大である。

符号化と復号

符号化はそれぞれの位置ごとに逆転を数えることで行える。

また、次のような方法でインプレースに行うこともできる（ただし、現実的には単純に数える以上に効率的であるわけではない）。

この方法では、まず各要素を昇順にソートしたときの $0$ から始まるインデックスへと置き換える。そして左から右へ順に、各エントリ $x$ について、それより右でかつ $x$ より大きいエントリから $1$ を引くことを繰り返す。たとえば、B, F, A, G, D, E, Cは1, 5, 0, 6, 3, 4, 2という数列に置き換えられ、次のように処理される。

${\begin{matrix}\mathbf {1} &5&0&6&3&4&2\\1&\mathbf {4} &0&5&2&3&1\\1&4&\mathbf {0} &4&2&3&1\\1&4&0&\mathbf {3} &1&2&0\\1&4&0&3&\mathbf {1} &2&0\\1&4&0&3&1&\mathbf {1} &0\\1&4&0&3&1&1&\mathbf {0} \\\end{matrix}}$

こうして、全エントリを処理し終わって得られた最後の行がレーマー符号である。デコードはこの逆を行えばよい。右から左へ各エントリ $x$ について、それより右にある $x$ 以上のエントリに $1$ を足すことを繰り返す。

出典

^ Lehmer, D.H. (1960), “Teaching combinatorial tricks to a computer”, Proc. Sympos. Appl. Math. Combinatorial Analysis, Amer. Math. Soc. 10: 179–193
^ Laisant, Charles-Ange (1888), “Sur la numération factorielle, application aux permutations” (フランス語), Bulletin de la Société Mathématique de France 16: 176–183

レーマー符号

符号

符号化と復号

関連項目

出典

関連文献