エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

ビジュアルプログラミング(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;
}