レーマー符号

レーマー符号の概要

組合せ数学の領域において、レーマー符号（Lehmer code）は、n 個の数のすべての置換を表現する手法の一つです。この名前は、数学者デリック・ヘンリー・レーマーに由来していますが、この符号の概念は1888年にはすでに認識されていました。

レーマー符号の構成

レーマー符号は、n 個の数の置換が持つ特性を活用しており、置換が持つ全ての順列の数は n!（n の階乗）として示されます。具体的には、置換 σ は、1 から n の数の並び (σ1, …, σn) を通じて表現されます。ただし、この並びには、同じ数を二度使用した可能性も含まれます。

レーマー符号は、置換の各要素について、どれだけの逆転が存在するかという指標を用いて符号化されます。ここでの「逆転」とは、要素の位置 i と j において i < j でありながら σi > σj となる組み合わせを指します。ここから、逆転の数を数えることで、レーマー符号は以下のように定義されます：

L(σ) = (L(σ)1, …, L(σ)n)
ここで
L(σ)i = # {j > i : σj < σi}

この定義により、L(σ)iは、σi よりも右に位置するエントリの中で、σi より小さい数の個数が計測されます。全体の逆転数は、L(σ)1からL(σ)nまでの合計で求められるため、これにより、特定の置換における逆転の数が明示されます。興味深いことに、これらの逆転の総和は、恒等順列に変換するために必要な隣接互換の数とも一致します。

符号化と復号化

レーマー符号の符号化は、逆転を計測することで実施されます。具体的には、各位置における逆転の数を数える方法が一般的です。このプロセスはインプレースで行うことも可能であり、実際には特に効率的な手法とされています。

このインプレース法では、まず順列を昇順にソートして得られる位置情報を使用し、そのインデックスに基づいて要素を置き換えます。次に、左から右に進む中で、各要素 x がその右に存在する特定の条件を基に1を引くという操作を繰り返します。たとえば、配列 [B, F, A, G, D, E, C] がそれぞれ [1, 5, 0, 6, 3, 4, 2] という数列に置き換えられ、この数列に基づいて逆転数を求めることが行われます。

全てのエントリを処理し終わった後、最終的に得られた行がレーマー符号として表されます。復号化はこの過程の逆を行い、エントリを右から左に進め、x に加算していくことで実施されます。

結論

レーマー符号は、組合せ数学の重要なツールであり、置換に関する逆転の計測と符号化に基づく形で構成されています。これにより、数学的な解析やアルゴリズムの設計における有用性が高まっています。

もう一度検索