検証的プログラミング(3)

置換のパリティー(3)

前回のコードを書き直して、ソートの中でチェックする項目を変更しました。ソートの中で使う条件をテストする項目を追加しました。

置換を表すクラスを Permutation とします。 の は固定とし、最初に設定します。互換を表すクラスを Exchanger、基本互換を表すクラスを Ladder とします。乱数で任意の置換を作成し、条件を満たすかどうかをチェックします。

共通関数

リストをコピーする

    function copy<T>(list: T[]): T[] {
        return Array.from(list);
    }

リストを生成する

    function generate<T>(length: number, generator: () => T): T[] {
        return Array.from(Array(length), (t: T) => generator());
    }

from から to までの整数のリストを作成する

    function rangefromto(from: number, to: number): number[] {
        return Array.from(Array(to - from + 1), (_, i) => from + i);
    }

から to までの整数のリストを作成する

    function rangeto(to: number): number[] {
        return rangefromto(1, to);
    }

(乱数で) max 以下の任意の正の整数を返す

    function any_positive_integer(max: number): number {
        return Math.floor(Math.random() * max) + 1;
    }

置換に変換することができるクラスを表すインターフェイス

    interface Permutable

置換に変換する

        get permutation(): Permutation;

基本互換の合成に分解する

        get ladder_composition(): Composition<Ladder>;

置換を表すクラス

    class Permutation implements Permutable

置換を表す整数のリスト

        public list: number[];

から までのリスト(最初に設定する)

        public static indices: number[] = [];

(乱数で) から までの任意の数を返す

        public static any_index(): number {
            return any_positive_integer(Permutation.indices.length);
        }

コンストラクタ

        public constructor(list: number[]) {
            this.list = copy(list);
        }

であるようなすべての組 を返す

        public get all_exchangers(): Exchanger[] {
            return rangeto(this.list.length - 1).flatMap(i => rangefromto(i + 1, this.list.length).map(j => new Exchanger([i, j])));
        }

であるようなすべての組 を返す

        public get all_ladders(): Ladder[] {
            return rangeto(this.list.length - 1).map(i => new Ladder(i));
        }

組 は転倒である( は から)

        public has_inversion(i: number, j: number): boolean {
            return this.list[i - 1] > this.list[j - 1];
        }

すべての転倒となる組を返す

        public get all_inversions(): Exchanger[] {
            return this.all_exchangers.filter(x => x.is_inversion_of(this));
        }

転倒となる基本互換が存在する

        public get has_ladder_inversion(): boolean {
            return this.all_ladders.some(x => x.is_inversion_of(this));
        }

転倒となる基本互換を返す

        public get find_ladder_inversion(): Ladder {
            return this.all_ladders.find(x => x.is_inversion_of(this)) as Ladder;
        }

(乱数で)リストの任意の要素を返し、その要素は削除する

        public static any_element_of(list: number[]): number {
            var n: number = any_positive_integer(list.length);
            return list.splice(n - 1, 1)[0];
        }

(乱数で)任意の置換を返す

        public static get any(): Permutation {
            var list: number[] = copy(Permutation.indices);
            return new Permutation(generate(Permutation.indices.length, () => Permutation.any_element_of(list)));
        }

恒等置換

        public static get identity(): Permutation {
            return new Permutation(Permutation.indices);
        }

逆方向の合成

        public compose(perm: Permutation): Permutation {
            return new Permutation(Permutation.indices.map(i => this.list[perm.list[i - 1] - 1]));
        }

置換に変換する

        public get permutation(): Permutation {
            return this;
        }

基本互換の合成に分解する

        public get ladder_composition(): Composition<Ladder> {
            return new Sorter(this).sort();
        }

パリティー(バブルソートによるパリティー)

        public get parity() {
            return this.ladder_composition.parity;
        }

要素を入れ替える( は から)

        public exchange(i: number, j: number): void {
            var tmp: number = this.list.splice(i - 1, 1, this.list[j - 1])[0];
            this.list.splice(j - 1, 1, tmp);
        }

互換を表すクラス(index1 と index2 を入れ替える互換)

    class Exchanger implements Permutable

入れ替える要素のインデックス

        private index1: number;
        private index2: number;

互換を表すリストを返す(内容の確認用)

        public get list(): number[] {
            return [this.index1, this.index2];
        }

コンストラクタ

        public constructor(list: number[]) {
            this.index1 = list[0];
            this.index2 = list[1];
        }

置換に変換する

        public get permutation(): Permutation {
            var perm: Permutation = Permutation.identity;
            perm.exchange(this.index1, this.index2);
            return perm;
        }

基本互換の合成に分解する

        public get ladder_composition(): Composition<Ladder> {
            return new Sorter(this.permutation).sort();
        }

パリティー(バブルソートによるパリティー)

        public get parity() {
            return this.ladder_composition.parity;
        }

perm の転倒である

        public is_inversion_of(perm: Permutation): boolean {
            return perm.has_inversion(this.index1, this.index2);
        }

要素を入れ替える

        public exchange(perm: Permutation): void {
            perm.exchange(this.index1, this.index2);
        }

(乱数で)任意の互換を返す

        public static get any(): Exchanger {
            var list: number[] = copy(Permutation.indices);
            return new Exchanger(generate(2, () => Permutation.any_element_of(list)));
        }

基本互換を表すクラス(index と index + 1 を入れ替える基本互換)

    class Ladder implements Permutable {

入れ替える要素のインデックス

        private index: number;

基本互換を表すリストを返す(内容の確認用)

        public get list(): number[] {
            return [this.index];
        }

コンストラクタ

        public constructor(index: number) {
            this.index = index;
        }

置換に変換する

        public get permutation(): Permutation {
            var perm: Permutation = Permutation.identity;
            perm.exchange(this.index, this.index + 1);
            return perm;
        }

基本互換の合成に分解する

        public get ladder_composition(): Composition<Ladder> {
            return new Sorter(this.permutation).sort();
        }

パリティー(バブルソートによるパリティー)

        public get parity() {
            return this.ladder_composition.parity;
        }

perm の転倒である

        public is_inversion_of(perm: Permutation): boolean {
            return perm.has_inversion(this.index, this.index + 1);
        }

要素を入れ替える

        public exchange(perm: Permutation): void {
            perm.exchange(this.index, this.index + 1);
        }

(乱数で)任意の基本互換を返す

        public static get any(): Ladder {
            var n: number = any_positive_integer(Permutation.indices.length - 1);
            return new Ladder(n);
        }

パリティーを表すクラス

    class Parity

パリティーを表す数値(0(偶数)または1(奇数))

        public bit: number;

コンストラクタ

        public constructor(number: number) {
            this.bit = number % 2; 
        }

パリティーが等しい

        public equal(parity: Parity): boolean {
            return this.bit == parity.bit;
        }

奇数のパリティー

        public static get odd() {
            return new Parity(1);
        }

置換を合成したものを表すクラス

    class Composition<T extends Permutable>

合成される置換のリスト

        public perm_list: T[];

コンストラクタ

        public constructor(perm_list: T[]) {
            this.perm_list = copy(perm_list);
        }

合成する(リストに追加)

        public compose(perm: T): void {
            this.perm_list.push(perm);
        }

合成される置換のリストをすべて合成した置換

        public get product(): Permutation {
            return this.perm_list.map(p => p.permutation).reduce((prod: Permutation, perm: Permutation) => prod.compose(perm), Permutation.identity);
        }

パリティー(リストの長さのパリティー)

        public get parity(): Parity {
            return new Parity(this.perm_list.length);
        }

互換の合成に分解したものを表すクラス

    class ExchangerComposition

互換の合成のリストの最大の長さ(最初に設定する)

        public static max_length: number = 1;

(乱数で)互換の合成のリストを作成する(長さは max_length 以下)

        public static get any(): Composition<Exchanger> {
            var len: number = any_positive_integer(ExchangerComposition.max_length);
            return new Composition<Exchanger>(generate(len, () => Exchanger.any));
        }

バブルソートを行うクラス

    class Sorter

バブルソートを行う置換

        private perm: Permutation;

ソートの結果を表す基本互換のリスト

        private ladder_composition: Composition<Ladder> = new Composition<Ladder>([]);

コンストラクタ

        public constructor(perm: Permutation) {
            this.perm = new Permutation(perm.list); // リストをコピー
        }

すべての転倒となる組を返す(確認用)

        public get all_inversions(): Exchanger[] {
            return this.perm.all_inversions;
        }

バブルソートを行う

        public sort(): Composition<Ladder> {
            var icount: number = this.all_inversions.length;
            this.all_inversions.forEach((x, i) => {
                console.assert(this.all_inversions.length + i == icount, "ソートテスト(1)：転倒数が間違っている %d", this.perm.all_inversions.length);
                console.assert(i == this.ladder_composition.perm_list.length, "ソートテスト(2)：基本互換の個数が間違っている");
                console.assert(this.perm.has_ladder_inversion, "ソートテスト(3)：転倒となる基本互換が存在しない");
                var ladder: Ladder = this.perm.find_ladder_inversion;
                ladder.exchange(this.perm);
                this.ladder_composition.compose(ladder);
            });
            console.assert(this.all_inversions.length == 0, "ソートテスト(4)：ソート失敗(転倒数は %d)", this.all_inversions.length);
            return this.ladder_composition;
        }
    }

テスト

テスト(1)：隣接する要素の転倒がなければ転倒数は 0

    function ladder_inversion_exists_test(): (number | boolean | object)[][] {
        var perm: Permutation = Permutation.any;
        var inversion_exists: boolean = perm.all_inversions.length != 0;
        var test: boolean = perm.has_ladder_inversion == inversion_exists;
        console.assert(test, "テスト(1)：隣接する要素の転倒がなければ転倒数は 0");
        return [perm.list, [inversion_exists, test]];
    }

テスト(2)：任意の置換の転倒数は、任意の基本互換との合成によって増減する

    function ladder_inversion_test(): (number | boolean | object)[][] {
        var perm: Permutation = Permutation.any;
        var ladder: Ladder = Ladder.any;
        var n: number = ladder.is_inversion_of(perm) ? -1 : 1;
        var ladder_perm: Permutation = ladder.permutation;
        var perm2: Permutation = perm.compose(ladder_perm);
        var count: number = new Sorter(perm).all_inversions.length;
        var count2: number = new Sorter(perm2).all_inversions.length;
        var test: boolean = count + n == count2;
        console.assert(test, "テスト(2)：置換の転倒数は、任意の基本互換との合成によって増減する");
        return [perm.list, ladder.list, ladder_perm.list, perm2.list, [n, count, count2, test]];
    }

テスト(3)：任意の置換のパリティーと、その置換と任意の基本互換の合成のパリティーは異なる

    function ladder_parity_test(): (number | boolean | object)[][] {
        var perm: Permutation = Permutation.any;
        var ladder: Ladder = Ladder.any;
        var ladder_perm: Permutation = ladder.permutation;
        var perm2: Permutation = perm.compose(ladder_perm);
        var parity: Parity = perm.parity;
        var parity2: Parity = perm2.parity;
        var test: boolean = !parity.equal(parity2);
        console.assert(test, "テスト(3)：置換とその置換と基本互換の合成のパリティーは異なる");
        return [perm.list, ladder.list, ladder_perm.list, perm2.list, [parity.bit, parity2.bit, test]];
    }

テスト(4)：任意の互換のパリティーは 奇数

    function exchanger_parity_test(): (number | boolean | object)[][] {
        var exchanger: Exchanger = Exchanger.any;
        var parity: Parity = exchanger.parity;
        var test: boolean = parity.equal(Parity.odd);
        console.assert(test, "テスト(4)：互換のパリティーは奇数");
        return [exchanger.list, [parity.bit, test]];
    }

テスト(5)：任意の置換を互換の合成で表したとき、互換の個数のパリティーと置換のパリティーは一致する

    function exchangers_parity_test(): (number | boolean | object)[][] {
        var exchangers: Composition<Exchanger> = ExchangerComposition.any;
        var product: Permutation = exchangers.product;
        var parity: Parity = product.parity;
        var parity2: Parity = exchangers.parity;
        var test: boolean = parity.equal(parity2);
        console.assert(test, "テスト(5)：互換の個数のパリティーは置換のパリティーと一致");
        return [exchangers.perm_list.map(x => x.list), product.list, [parity.bit, parity2.bit, test]];
    }

群論 日評ベーシック・シリーズ

代数学入門---先につながる群，環，体の理論NBS 日評ベーシック・シリーズ