Skip to content →

転倒数の偶奇を線形で求めるアルゴリズム

\((1, 2, \ldots, N)\) の順列 \(P\) の転倒数の偶奇(置換の偶奇)は線形で求められます。

辺 \((i, P_i)\) \((1 \leq i \leq N)\) を貼った有向グラフを \(G\) とします。各頂点の入次数・出自数が共に1なので、\(G\) は交わらない有向閉路の和で表せます。頂点数 \(k\) の閉路
\(a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_k \rightarrow a_1\)
に着目します。順列の先頭から \(a_1\) 番目と \(a_2\) 番目を swap すると、自己ループ
\(a_1 \rightarrow a_1\)
と長さ \(k-1\) の閉路
\(a_2 \rightarrow a_3 \rightarrow \cdots \rightarrow a_k \rightarrow a_2\)
に分かれます。従って、長さ \(k-1\) の閉路で再帰的に swap をすると、長さ \(k\) の閉路は、\(k-1\) 回の swap で自己ループ(恒等置換)に分解できます。よって、長さ \(k\) の有向閉路の転倒数の偶奇は \(k-1\bmod 2\) と等しいです。各有向閉路の和を取ると、\(G\) の転倒数の偶奇は (頂点数)−(有向閉路の個数)を \(2\) で割った余りに等しいです。これは、BFS によって線形時間で求められます。実装で楽をしたければ、Union Find でも良いと思います。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA