レーマー符号 (Lehmer code)

レーマー符号とは

レーマー符号とは、並べ替えを符号化する方法の一つ。普通並べ替えを表すのには、シーケンス番号の列を使ったりするが、それだと基の列との差分の大きさがわかりにくい。レーマー符号だと、それがわかりやすい、ということらしい。

レーマー符号は、次のように定義される。

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

ここで $L(\sigma)_{i}$ は $\sigma_{i+1},\ldots,\sigma_{n}$ のうち $\sigma_{i}$よりも小さいものの個数である。と言われてもよくわからん。。

日本語のWikipediaにはエンコード、デコードの方法が書かれていないが、英語版を見ると、割に簡単な再帰で書ける事がわかる。Pythonで書くとこんな感じ。

def lehmer(input):
    if len(input) > 1:
        head = input[0]
        rest = input[1:]
        rest = [r-1 if r>head else r for r in rest]
        return [head] + lehmer(rest)
    else:
        return input

デコードも同様に再帰で書ける。

def lehmer_decode(input):
    if len(input) > 1:
        head = input[0]
        rest = lehmer_decode(input[1:])
        rest = [r+1 if r >= head else r for r in rest]
        return [head] + rest
    else:
        return input

例

試してみよう。identity projection は0の列になる。

>>> lehmer([0,1,2,3,4,5,6])
[0, 0, 0, 0, 0, 0, 0]
>>> lehmer_decode([0,0,0,0,0,0,0])
[0, 1, 2, 3, 4, 5, 6]

6だけが一番前に行った列[6,0,1,2,3,4,5]を考えてみよう。これはアイテムごとに比較すると、もとの列と一致している点はどこにもないが、列としては一つずれているだけだ。レーマー符号にすると次のようになる。

>>> lehmer([6,0,1,2,3,4,5])
[6, 0, 0, 0, 0, 0, 0]

これだと最初に大きくずれたあとは正しく並んでいることがわかる。