ビジュアルプログラミング(25) - エレファント・コンピューティング調査報告

偶置換・奇置換(2)

「群論の計算(9) - エレファント・コンピューティング調査報告」や「エレファントな線形代数(5) - エレファント・コンピューティング調査報告」では以下のようなことを説明しています。

ここでは、「バブルソート」は隣接する2つの要素を交換することを繰り返すものとします。

リストの $i$ 番目の要素を $a_i$ と書くとき、集合
$\{( i,j) \mid i < j \ かつ \ a_i > a_j \}$
の元の個数をリストの「転倒数」と呼びます。TypeScriptで書くと以下のようになります。

function inversion_count(list: number[]): number {
    var count = 0;
    for (var i = 0; i < list.length - 1; i++) {
        for (var j = i + 1; j < list.length; j++) {
            if (list[i] > list[j]) {
                count++;
            }
        }
    }
    return count;
}

隣接する2つの要素を交換すると、「転倒数」は 1 増加、または 1 減少します。「バブルソート」では減少する場合に交換するので、「バブルソート」の交換の回数と「転倒数」は一致します。

ここまでをまめると、まず「バブルソート」の交換の回数が偶数である置換は偶置換、奇数である置換は奇置換と定義します。「バブルソート」の一回の交換によって「転倒数」は 1 減少するので、「バブルソート」は終了して、任意の置換は偶置換または奇置換となり、偶置換のとき「転倒数」は偶数、奇置換のとき「転倒数」は奇数となります。

次にある置換 $\sigma$ とある互換(2つの要素を交換する置換) $\mu$ の合成 $\sigma\mu$ を考えます。 $\sigma$ をリストで表したものの $a$ の位置と $b$ の位置を入れ替える操作を、隣接する要素を入れ替える操作の合成で表します。TypeScriptで書くと以下のようになります。

function exchange_neighbor(list: number[], a: number, b: number): void {
    // 隣の要素同士を交換して a と b を交換
    // a, b は 0 から、a ≦ b
    for (var i = a; i < b; i++) {
        exchange(list, i, i + 1);
    }
    for (var i = b - 1; i > a; i--) {
        exchange(list, i - 1, i);
    }
}

隣接する要素を入れ替える操作の回数は $2(b-a-1)+1$ となります。よって $\sigma$ が偶置換のときは $\sigma\mu$ は奇置換、 $\sigma$ が奇置換のときは $\sigma\mu$ は偶置換となります。帰納的に、偶数個の互換の合成は偶置換、奇数個の互換の合成は奇置換となります。