この記事のなかでは,互換,すなわち2つの位置だけを入れ替えるような置換のことをswapと呼ぶことにする.*1
長さnの順列について、swap列がを整列するとは、
となることであるとする.
命題1: 長さのサイクルに対して,swapを一回適用したときにできる順列をサイクル分解したときのサイクルの長さの和は少なくともであり,またにするようなは存在する.
命題1を証明する.
について,(場合1)かつか,
(場合2)だがのどちらかが成り立つ.
場合1を考える.と仮定して一般性を失なわない.
このとき,のサイクル分解を考えると,
というサイクルと,
というサイクルとに分解される.
ここで,場合1の仮定よりどちらの長さもきちんと2以上になっていることに注意する.
よって,サイクルの長さの和はとなり,これは以上である.
場合2を考える.と仮定して一般性を失なわない.
このとき,という長さのサイクルだけができる.
よって,サイクルの長さの和はとなる.これは,サイクルの長さの和をにするようなの存在も示している.
命題1の証明おわり.
命題2: 長さn(>1)のサイクルの整列に必要なswap列の長さの最小はである.
命題2を証明する.その順列が整列されていることと,そのサイクル分解のサイクルの長さの和が0であることとは等価である.
のときは明らか.を考える.
命題1は,1回のswapではサイクル分解のサイクルの長さの和は高々1しか減らないこと,またそれを1減らすswapがあることを主張しているので,そこから分かる.命題2の証明おわり.
命題3: 順列を整列するには,そのサイクル分解毎に整列するのが最短である.
命題3を証明する.順列に対するswapのうち,2つのサイクル分解をまぜるようなものを考える.
の分解には,ととその他のサイクルがあり,はとを入れ替えるとして一般性を失なわない.このとき,のサイクル分解は,
と
となり,サイクル分解のサイクルの長さの和は減少しない.
よって,サイクル分解毎に整列し,サイクルの長さの和を1ずつ減少させるのが最適である.
命題3の証明おわり.