レーマー符号のソースを表示

[[数学]]とくに[[組合せ数学]]において、'''レーマー符号'''（レーマーふごう、{{lang-en-short|Lehmer code}}）は、''n'' 個の数のすべての[[置換 (数学)|置換]]を符号化する方法の一つである。レーマー符号という名前は{{仮リンク|デリック・ヘンリー・レーマー|en|Derrick Henry Lehmer}}に由来するが、この符号は少なくとも1888年には知られていた<ref name="lehmer"/><ref name="laisant"/>。

== 符号 ==
レーマー符号は、''n'' 個の数の置換が
:<math>n!=n\times(n-1)\times\cdots\times2\times1</math>
個存在するという事実を利用している。置換 ''σ'' は 1, …, ''n'' の像の列 (''σ''<sub>1</sub>, …, ''σ''<sub>''n''</sub>) によって表すなら、''n'' 個の数の並びによって符号化されることになる。しかし、こうした並びには置換を表さないもの（同じ数を二度使ったもの）も含まれている。ここで考察する符号は、先頭の数を ''n'' 個の数から選び、次の数は {{math|''n'' − 1}} 個の数から選び、そうしていって、最後の数はたった1個の数から選んでできるものである。<!--ここに訳していない文がある-->

レーマー符号は、次の列である。
:<math>L(\sigma)=(L(\sigma)_1,\ldots,L(\sigma)_n)\quad\text{where}\quad L(\sigma)_i=\#\{ j>i : \sigma_j<\sigma_i \}</math>
記号 ''L''(''σ'')<sub>''i''</sub> は、''σ''<sub>''i''+1</sub>, …, ''σ''<sub>''n''</sub> のうち ''σ''<sub>''i''</sub> より小さいものの個数である。

{{math|''i'' &lt; ''j''}} かつ {{math|''σ''<sub>''i''</sub> &gt; ''σ''<sub>''j''</sub>}} である添字の組 {{math|''i'' &lt; ''j''}}  を ''σ'' の'''逆転'''と呼び、''L''(''σ'')<sub>''i''</sub>は、逆転(''i'',''j'')がいくつあるかを表す（''i''は固定し''i''を変化させる）。このことから{{math|''L''(''σ'')<sub>1</sub> + ''L''(''σ'')<sub>2</sub> + … + ''L''(''σ'')<sub>''n''</sub>}} は ''σ'' に逆転がいくつ現れるかを表していることが分かる。これは、恒等順列に変換するために必要な隣接互換の数と等しい。位置 ''i''の値が0であればそこから右での最小であり（すなわち{{math|''σ''<sub>''i''</sub>}}はその右にあるどの{{math|''σ''<sub>''j''</sub>}}よりも小さい）、位置 ''i''での値{{math|''n'' − ''i''}}はそこから右での最大である。<!--いくつかの文は訳していない-->
<!-- 最終段落も訳していない -->

== 符号化と復号 ==


<!-- 抄訳 -->

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

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

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

<math> \begin{matrix}
  \mathbf1&5&0&6&3&4&2\\
  1&\mathbf4&0&5&2&3&1\\
  1&4&\mathbf0&4&2&3&1\\
  1&4&0&\mathbf3&1&2&0\\
  1&4&0&3&\mathbf1&2&0\\
  1&4&0&3&1&\mathbf1&0\\
  1&4&0&3&1&1&\mathbf0\\
\end{matrix}
</math>

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



== 関連項目 ==
*[[階乗進法]]

== 出典 ==
{{Reflist|refs=
<ref name=lehmer>
{{Citation
 | last=Lehmer
 | first=D.H.
 | title=Teaching combinatorial tricks to a computer
 | journal=Proc. Sympos. Appl. Math. Combinatorial Analysis, Amer. Math. Soc. 
 | volume=10
 | year=1960
 | pages=179–193
 }}
</ref>

<ref name="laisant">
{{Citation
 | language=fr
 | last=Laisant
 | first=Charles-Ange
 | title=Sur la numération factorielle, application aux permutations
 | journal=Bulletin de la Société Mathématique de France
 | volume=16
 | issue=
 | year=1888
 | pages=176–183
 | url=http://www.numdam.org/item?id=BSMF_1888__16__176_0
 }}
</ref>

}}

== 関連文献 ==
*{{Citation
 | last=Mantaci
 | first=Roberto
 | title=A permutation representation that knows what "Eulerian" means
 | journal=Discrete Mathematics and Theoretical Computer Science
 | issue=4
 | year=2001
 | pages=101–108
 | url=http://www.dmtcs.org/volumes/abstracts/pspapers/dm040203.ps
 }}
*{{ Citation
 | last1=Knuth
 | first1=Donald
 | author-link=ドナルド・クヌース
 | title=The art of computer programming
 | volume=3
 | publisher=Addison-Wesley
 | place=Reading
 | year=1981
 | pages=12–13
}}

{{Math-stub}}
{{デフォルトソート:れえまあふこう}}
[[Category:組合せ論]]
[[Category:順列]]
[[Category:数学に関する記事]]