ビジュアルプログラミング(27) - エレファント・ビジュアライザー調査記録

偶置換・奇置換(4)

以下のコード(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;
}

以下のコード(TypeScript)はバブルソートで転倒数の回数だけ要素を入れ替えて、その変換の基本互換(隣接する2つの要素を入れ替える互換)のリストを返します。これは有限回の繰り返しなので終了します。基本互換の数は転倒数と一致するので、終了するとソートが完了しています。

function sort_exch_list(list: number[]): number[][] {
    var exch_list: number[][] = [];
    function exchange(list: number[], i: number, j: number): void {
        // i, j は 0 から
        count++;
        //comp_list.push([list[i], list[j]]);
        exch_list.push([i + 1, j + 1]);
        var tmp: number = list[i];
        list[i] = list[j];
        list[j] = tmp;
    }
    var icount: number = inversion_count(list);
    for (var k = 0; k < icount; k++) {
        for (var i = 0; i < list.length - 1; i++) {
            if (list[i] > list[i + 1]) {
                break;
            }
        }
        if (i < list.length - 1) {
            exchange(list, i, i + 1);
        } else {
            break;
        }
    }
    return exch_list;
}

以下のコード(TypeScript)は置換が偶置換か奇置換かと、バブルソートで得られる基本互換の個数が偶数か奇数かの関係を調べます。これは常に真となります。compose_list(xlist) は xlist に含まれるずべての互換の合成を表します。

function transposition_property(xlist: number[][]): boolean {
    // 互換のリスト xlist に対して条件が正しいかどうかを調べる
    return sort_exch_list(compose_list(xlist)).length % 2 == xlist.length % 2;
}