置換のパリティー(2)
置換を表すクラスを 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 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 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(); }
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(); }
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; }
1(奇数)のパリティー
public static get one() { 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); }
互換の合成に分解したものを表すクラス
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 inversion_count(): number { return this.perm.all_exchangers.filter(x => x.is_inversion_of(this.perm)).length; // 転倒数 }
バブルソートを行う
public sort(): Composition<Ladder> { var icount: number = this.inversion_count; for (var k = 0; k < icount; k++) { console.assert(k + this.inversion_count == icount, "転倒数が間違っている %d", this.inversion_count); if (!this.perm.all_ladders.some(x => x.is_inversion_of(this.perm))) { break; } var ladder: Ladder = this.perm.all_ladders.find(x => x.is_inversion_of(this.perm)) as Ladder; ladder.exchange(this.perm); this.ladder_composition.compose(ladder); } console.assert(this.inversion_count == 0, "ソート失敗(転倒数は %d)", this.inversion_count); return this.ladder_composition; }
テスト
以下のテストを行います。
任意の置換の転倒数は、任意の基本互換との合成によって増減することのテスト
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).inversion_count; var count2: number = new Sorter(perm2).inversion_count; var test: boolean = count + n == count2; console.assert(test, "置換の転倒数は、任意の基本互換との合成によって増減する"); return [perm.list, ladder.list, ladder_perm.list, perm2.list, [n, count, count2, test]]; }
任意の置換のパリティーと、その置換と任意の基本互換の合成のパリティーは異なることのテスト
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, "置換とその置換と基本互換の合成のパリティーは異なる"); return [perm.list, ladder.list, ladder_perm.list, perm2.list, [parity.bit, parity2.bit, test]]; }
任意の互換のパリティーは 1 (奇数)であることのテスト
function exchanger_parity_test(): (number | boolean | object)[][] { var exchanger: Exchanger = Exchanger.any; var parity: Parity = exchanger.parity; var test: boolean = parity.equal(Parity.one); console.assert(test, "互換のパリティーは 1"); return [exchanger.list, [parity.bit, test]]; }
任意の置換を互換の合成で表したとき、互換の個数のパリティーと置換のパリティーは一致することのテスト
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, "互換の個数のパリティーは置換のパリティーと一致"); return [exchangers.perm_list.map(x => x.list), product.list, [parity.bit, parity2.bit, test]]; }