Title : Math::MatrixBool - Matrix of Booleans
|
Location : Home > Languages > Perl > Package Title : Math::MatrixBool - Matrix of Booleans |
|
Math::MatrixBool - ブール代数による行列演算
ブール代数による行列の演算
use Math::MatrixBool;
$new_matrix = new Math::MatrixBool($rows,$columns);
行列オブジェクトコンストラクタメソッド。例外は必要なメモリがアロケーションできない場合。
$new_matrix = Math::MatrixBool->new($rows, $columns);
行列オブジェクトコンストラクタメソッドを呼び出す場合の代替的方法。
$new_matrix = $some_matrix->new($rows, $columns);
さらに行列オブジェクトコンストラクタメソッドを呼び出す場合の代替的方法。（$some_matrix はこれによる影響を受けない）
$new_matrix = Math::MatrixBool->new_from_string($string);
本メソッドにより文字列から（すなわちキーボードやファイルやコードから）行列を読み込むことができる。
文法は以下の通り：
各行は "[ " で始まり、" ]\n" で終わり（ただし \n は改行を示し、" " は空白またはタブを示す）、１つ以上の数値を含み、それぞれは空白またはタブで区切られていなければならない。
空白やタブを追加することはできるが、コメントは追加できない。
数値は "0" または "1" に限る。
例：
$string = "[ 1 0 0 ]\n[ 1 1 0 ]\n[ 1 1 1 ]\n"; $matrix = Math::MatrixBool->new_from_string($string); print "$matrix";
これは以下を出力する。
[ 1 0 0 ] [ 1 1 0 ] [ 1 1 1 ]
しかしシェルで使うような「ヒアドキュメント（here-document）」文法を用いて簡単に書くこともできる。
$matrix = Math::MatrixBool->new_from_string(<<'MATRIX'); [ 1 0 0 0 0 0 1 ] [ 0 1 0 0 0 0 0 ] [ 0 0 1 0 0 0 0 ] [ 0 0 0 1 0 0 0 ] [ 0 0 0 0 1 0 0 ] [ 0 0 0 0 0 1 0 ] [ 1 0 0 0 0 0 1 ] MATRIX
行列内で変数を用いることもできる。
$c1 = $A1 * $x1 - $b1 >= 0 ?"1":"0"; $c1 = $A2 * $x2 - $b2 >= 0 ?"1":"0"; $c1 = $A3 * $x3 - $b3 >= 0 ?"1":"0"; $matrix = Math::MatrixBool->new_from_string(<<"MATRIX"); [ 1 0 0 ] [ 0 1 0 ] [ $c1 $c2 $c3 ] MATRIX
（行列のフォーマットを示すのに空白を使うかタブを使うかは自由）
本メソッドは行列に対する文字列化演算子 "" と同じ表現を用いることに注意。これは $string = "$matrix"; を用いて行列を文字列に変換することができることを意味する。また後で読み直すこともできる（すなわちファイルから！）
もし渡した文字列が上述の文法に従っていなければ例外処理を行い以下のような評価を行う。
print "Please enter your matrix (in one line): ";
$string = <STDIN>;
$string =~ s/\\n/\n/g;
eval { $matrix = Math::MatrixBool->new_from_string($string); };
if ($@)
{
print "$@";
# ...
# （エラー処理）
}
else
{
# 続き
}
または以下のように書いてもよい。
eval { $matrix = Math::MatrixBool->new_from_string(<<"MATRIX"); };
[ 1 0 0 ]
[ 0 1 0 ]
[ $c1 $c2 $c3 ]
MATRIX
if ($@)
# ...
実際のところ、キーボードからの行列の読み込みは、たくさんの "\n" を入力する必要があり、上記で示したメソッドは少し awk のようである。
よりよい方法はコードの断片にみることができる。
while (1)
{
print "\nPlease enter your matrix ";
print "(multiple lines, = done):\n";
eval { $new_matrix =
Math::MatrixBool->new_from_string(join('',)); };
if ($@)
{
$@ =~ s/\s+at\b.*?$//;
print "${@}Please try again.\n";
}
else { last; }
}
new_from_string() メソッドのありうるエラーメッセージは以下の通り。
Math::MatrixBool::new_from_string(): syntax error in input string Math::MatrixBool::new_from_string(): empty input string
もし入力文字列が列の数と異なる行の数が指定されれば STDERR に以下の警告が出力される。
Math::MatrixBool::new_from_string(): missing elements will be set to zero!
すべてがＯＫであればメソッドは指定した要素を含む（新しくアロケートされた）行列へのオブジェクト参照を返す。
($rows,$columns) = $matrix->Dim();
所与の行列の次数（行と列の数）を返す。
$matrix->Empty();
行列の全ての要素を "0" に設定する。
$matrix->Fill();
行列の全ての要素を "1" に設定する。
$matrix->Flip();
行列の全ての要素を、その補数に入れ替える。
$matrix->Zero();
行列の全ての要素を "0" に設定する。
$matrix->One();
主対角要素を 1 に、それ以外の要素を 0 に設定する。
この行列をかけても同じ行列になることに注意。（正方行列とする）
$matrix->Bit_On($row,$column);
所与の要素を "1" に設定する。
$matrix->Insert($row,$column);
Bit_On() のエイリアス。
$matrix->Bit_Off($row,$column);
所与の要素を quot;0" に設定する。
$matrix->Delete($row,$column);
Bit_Off() のエイリアス。
$boolean = $matrix->bit_flip($row,$column);
所与の要素の補数を求め、新しい値を返す。
$boolean = $matrix->flip($row,$column);
bit_flip() のエイリアス。
$boolean = $matrix->bit_test($row,$column);
所与の要素が設定されているかをテスト。
$boolean = $matrix->contains($row,$column);
所与の要素が設定されているかをテスト。bit_test() のエイリアス。
$boolean = $matrix->in($row,$column);
bit_test() のエイリアス。
$elements = $matrix->Number_of_elements();
所与の行列に含まれている要素の数を計算する。
$norm_max = $matrix->Norm_max();
所与の行列の最大ノルムを計算する。
$norm_one = $matrix->Norm_one();
所与の行列の 1-ノルムを計算する。
$matrix1->Addition($matrix2,$matrix3);
matrix2 と matrix3 の和を計算し結果を matrix1 に格納する。（置き換えも可）
$product_matrix = $matrix1->Multiplication($matrix2);
matrix1 と matrix2 の積を計算し、結果の新しい行列への参照を返す。内部的にはブール代数の ^ を用いる。
$product_matrix = $matrix1->Product($matrix2);
matrix1 と matrix2 の積を計算し、結果の新しい行列への参照を返す。内部的にはブール代数の | を用いる。
$closure = $matrix->Kleene();
所与の行列に対し反射的推移的閉包（the reflexive transitive closure）を計算し、結果を含む新しい行列を返す。（これではどうやっても元の行列は変更されない！）
Kleene のアルゴリズムの変法を利用している。このアルゴリズムについての詳細は Math::Kleene(3) を参照のこと！
本アルゴリズムは主にグラフ理論で利用される。行列内の各位置はグラフにおける２つの頂点間の可能な接続（辺）に対応する。
行列における各位置は対応する辺がグラフの一部であれば "1" を、そうでなければ "0" で示す。
グラフの頂点から他の頂点へのパスがあるかを確認するためにこの行列の閉包を計算する。
他の分野における Kleene のアルゴリズムの適用例については Math::MatrixReal(3), DFA::Kleene(3), Math::Kleene(3) を見よ。
$matrix1->Union($matrix2,$matrix3);
matrix2 と matrix3 の結合を計算し、結果を matrix1 に格納する。（置き換えも可）
$matrix1->Intersection($matrix2,$matrix3);
matrix2 と matrix3 の交差を計算し、結果を matrix1 に格納する。（置き換えも可）
$matrix1->Difference($matrix2,$matrix3);
matrix2 「引く」 matrix3 ( = matrix2 \ matrix3 ) を計算し、結果を matrix1 に格納する（置き換えも可能）。
これは集合としての差であって、行列としての差でないことに注意すること！ Matrix としての差はブール代数における行列の加算と同じである。
$matrix1->ExclusiveOr($matrix2,$matrix3);
matrix2 と matrix3 の排他的論理和（ブール代数における和と同じ）を計算し、結果を matrix1 に格納する（置き換えも可能）。
$matrix1->Complement($matrix2);
matrix2 の補数を計算し、結果を matrix1 に格納する（置き換えも可能である）。
$matrix1->Transpose($matrix2);
matrix2 の転置を計算し、matrix1 に結果を格納する（行列が正方であれば置き換えも可能）。一般には、matrix2 との関係で行の数と列の数が入れ替わる。
$boolean = $matrix1->equal($matrix2);
matrix1 が matrix2 と同じであることを確認。
$boolean = $matrix1->subset($matrix2);
matrix1 が matrix2 の部分集合であることを確認。
$boolean = $matrix1->inclusion($matrix2);
"subset()" のエイリアス。廃止予定。
$boolean = $matrix1->lexorder($matrix2);
matrix1 が辞書的に matrix2 より前に来るか否かを確認する。すなわち２つの行列を表す２つのビットベクトルが２つの２進数表現における大きな数と見なされて比較され、 if (matrix1 <= matrix2) を評価する。
（これは勝手な順序関係であることに留意すること）
$result = $matrix1->Compare($matrix2);
matrix1 と matrix2 とを辞書的に比較し、 if (matrix1 < matrix2), (matrix1 == matrix2), (matrix1 > matrix2) に従い、それぞれ -1, 0, 1 を返す。
（また、２つの行列を表す２つのビットベクトルが２つの２進数表現における大きな数と見なされて比較される。）
$matrix1->Copy($matrix2);
既存の matrix1 に対し matrix2 の中身を複写する。
$new_matrix = $some_matrix->Shadow();
some_matrix と同じ大きさで新規かつ空の行列へのオブジェクト参照を返す。
$twin_matrix = $some_matrix->Clone();
some_matrix と同じ大きさで新規の行列へのオブジェクト参照を返す。some_matrix の中身は新しい行列に複製される。
*
ヒント：全て小文字のメソッド名はブール返り値を示す！（もちろん new() 及び new_from_string() を除く！）
行列を用いた計算を行うために明示的なメソッド呼び出しをする代わりにオーバーロードされた演算子を用いる方法については下のオーバーロードされる演算子を参照のこと！
このクラスは任意の大きさのブール行列を動的に生成し、それらに関する基本演算を実施する。
行列を用いた計算を行うために明示的なメソッド呼び出しをする代わりにオーバーロードされた演算子を用いる方法については下のオーバーロードされる演算子を参照のこと！
行列の計算が本モジュールで用いて明示的に呼び出されて実行されるだけではなく、「魔法の」数値的・関係演算子で実行することもできる。
たとえば
$matrix1 = Math::MatrixBool->new($rows,$columns); $matrix2 = Math::MatrixBool->new($rows,$columns); $matrix3 = Math::MatrixBool->new($rows,$columns); [...] $matrix3->Multiplication($matrix1,$matrix2);
と書く代わりに次のように書くことができる。
$matrix1 = Math::MatrixBool->new($rows,$columns); $matrix2 = Math::MatrixBool->new($rows,$columns); [...] $matrix3 = $matrix1 * $matrix2;
これが全てだ。
ここに全ての「魔法の」オー場ロードされた演算子とその意味を記す。
単項演算子：'-', '~', 'abs', testing, '!', '""'
２項（算術）演算子：'+', '*', '|', '-', '&', '^'
２項（関係）演算子：'==', '!=', '<', '<=', '>', '>='
２項（関係）演算子：'cmp', 'eq', 'ne', 'lt', 'le', 'gt', 'ge'
上記リストの２項演算子の引数はともに行列であることに注意。数値または他の型のデータは引数として許されておらず、エラーメッセージを生成する。
-, 単項マイナス／補数 ( $matrix2 = -$matrix1; )
単項演算子 '-' は所与の行列の補数を計算する。
~, 転置 ( $matrix2 = ~$matrix1; )
演算子 '~' は所与の行列の転置を求める。
abs, 絶対値 ( $no_of_elem = abs($matrix); )
ここで、行列の絶対値とは所与の行列に含まれる要素の数として定義される。行列のノルムではない！
test, ブールテスト ( if ($matrix) { ... } )
あたかもブール値であるかのように行列をテストすることができる。
これには特別な演算子は不要で、Perl は自動的に "$matrix" が "Math::MatrixBool" クラスまたはその導出クラスのオブジェクトへの括弧つき参照であれば、本パッケージの適切なメソッドを呼び出す。
この演算は所与の行列が殻でなければ true (1) を返し、そうでなければ false ('') を返す。
!, 否定のブールテスト ( if (! $matrix) { ... } )
あたかもブール値であるかのように否定のテストを実施する。たとえば
if (! $matrix) { ... }
unless ($matrix) { ... } # inter内部的には上記と同じ
この演算は所与の行列が空でなければ true (1) を返し、そうでなければ false ('') を返す。
"", 文字列化 ( print "$matrix"; )
ダブルクォーテーションで行列のオブジェクト参照のはさんだとき、所与の行列の文字列表現を求めることが可能である。
Note that 行列の文字列表現は一般には複数行にわたる。（すなわち、列の各行の終わりを示す文字 "\n" を含む文字列に変換する。）
例：
$matrix = new Math::MatrixBool(5,6); $matrix->One(); print "$matrix";
これは以下のような出力となる。
[ 1 0 0 0 0 0 ] [ 0 1 0 0 0 0 ] [ 0 0 1 0 0 0 ] [ 0 0 0 1 0 0 ] [ 0 0 0 0 1 0 ]
+, 加算 ( $matrix3 = $matrix1 + $matrix2; )
演算子 '+' は２つの行列の和を計算する。
例：
$all = $odd + $even; $all += $odd; $all += $even;
行列に数を足すことは無意味であるので、演算子 '++' はエラーメッセージを出力することに注意すること。
*, 乗算 ( $matrix3 = $matrix1 * $matrix2; )
演算子 '*' は２つの行列の積を計算する。
例：
$test = $one * $one; $test *= $one; $test *= $test;
以下のように行の数と対応する列の数が同じであることに注意すること。
$matrix_3 = $matrix_1 * $matrix_2;
[ 2 2 ]
[ 2 2 ]
[ 2 2 ]
[ 1 1 1 ] [ 3 3 ]
[ 1 1 1 ] [ 3 3 ]
[ 1 1 1 ] [ 3 3 ]
[ 1 1 1 ] [ 3 3 ]
すなわち、行列 #1 の列の数は行列 #2 の行の数と同じであり、結果の行列 #3 の列の数はそれぞれ行列 #1 の行の数と列 #2 の列の数によって定まる。
ベクトルは１つの列または１つの行のみをもつ行列と見なせるので、行列とベクトルの乗算も計算することができる。
|, 結合 ( $matrix3 = $matrix1 | $matrix2; )
演算子 '|' は２つの行列の結合を計算するために用いられる。
例：
$all = $odd | $even; $all |= $odd; $all |= $even;
-, 差 ( $matrix3 = $matrix1 - $matrix2; )
演算子 '-' は２つの行列の差を計算する。すなわち
0 - 0 == 0 0 - 1 == 0 1 - 0 == 1 1 - 1 == 0
それぞれが対応する要素である。
例：
$odd = $all - $even; $all -= $even;
行列から数を減じることは無意味であるので、演算子 '++' はエラーメッセージを出力することに注意すること。
&, 共通部分 ( $matrix3 = $matrix1 & $matrix2; )
演算子 '&' は２つの行列の（対応する要素の）共通部分を計算するのに用いられる。
例：
$rest = $all & $even; $all &= $even;
^, 排他的論理和 ( $matrix3 = $matrix1 ^ $matrix2; )
演算子 '^' は２つの行列の（対応する要素の）排他的論理和を計算するのに用いられる。
実質的に、この演算がブール代数における２つの和の計算を指定する。
例：
$odd = $all ^ $even; $all ^= $even;
==, 等しいことの確認 ( if ($matrix1 == $matrix2) { ... } )
この演算子は２つの行列が等しいかをテストする。
演算子をオーバーロードしなければ、( $matrix1 == $matrix2 ) は同じオブジェクトへの２つの参照を比較することになることに注意すること！
演算子をオーバーロードしておくと、( $matrix1 == $matrix2 ) は２つの行列が正確に同じ要素を持つか否かを確認する。
!=, 等しくないことの確認 ( if ($matrix1 != $matrix2) { ... } )
この演算子は２つの行列が異なることを確認する。
２つの行列が異なるか否かを確認するのであって、２つの参照が異なるかを確認するのではないことに注意すること。
<, 真部分集合であることの確認 ( if ($matrix1 < $matrix2) { ... } )
この演算子は $matrix1 が $matrix2 の真部分集合であるかを確認する。すなわち $matrix1 の要素は $matrix2 にも含まれるが、$matrix2 に含まれる要素で $matrix1 に含まれない要素があるかを確認する。
例：
[ 1 0 0 0 0 ] [ 1 0 0 0 1 ] [ 0 1 0 0 0 ] [ 0 1 0 0 0 ] [ 0 0 1 0 0 ] は [ 0 0 1 0 0 ] の真の部分集合であるが、 [ 0 0 0 1 0 ] [ 0 0 0 1 0 ] [ 1 0 0 0 1 ] [ 1 0 0 0 1 ] [ 1 0 0 0 0 ] [ 1 0 0 0 1 ] [ 0 1 0 0 0 ] [ 0 1 0 0 0 ] [ 0 0 1 0 0 ] は [ 0 0 1 0 0 ] の部分集合ではない。 [ 0 0 0 1 0 ] [ 0 0 0 1 0 ] [ 1 0 0 0 1 ] [ 0 0 0 0 1 ]
（逆は真ではない！）
[ 1 0 0 0 1 ] [ 1 0 0 0 1 ] [ 0 1 0 0 0 ] [ 0 1 0 0 0 ] [ 0 0 1 0 0 ] は [ 0 0 1 0 0 ] の部分集合 [ 0 0 0 1 0 ] [ 0 0 0 1 0 ] [ 1 0 0 0 1 ] [ 1 0 0 0 1 ]
しかし２つの行列が恒等であれば真部分集合でない。
<, 部分集合であることの確認 ( if ($matrix1 <= $matrix2) { ... } )
この演算子は $matrix1 が $matrix2 の部分集合であるかを確認する。すなわち $matrix1 の要素が $matrix2 にも含まれるかを確認する。
２つの行列が同じであれば "true" と評価する。
>, 真上位集合であることの確認 ( if ($matrix1 > $matrix2) { ... } )
この演算子は $matrix1 が $matrix2 の真上位集合であるかを確認する。すなわち $matrix2 のあらゆる要素が $matrix1 に含まれるが $matrix1 の要素で $matrix2 に含まれないものがあることを確認する。
($matrix1 > $matrix2) は($matrix2 < $matrix1) と同じである。
>=, 上位集合であることの確認 ( if ($matrix1 >= $matrix2) { ... } )
cmp, 比較 ( $result = $matrix1 cmp $matrix2; )
この演算子は２つの行列を辞書的に比較する。すなわち２つの行列を表す２つのビットベクトルを２つの大きな（符号なし）数の２進数表現と見なし、$matrix1 に対応する数が $matrix2 に対応する数よりも小さければ "-1"を、２つの行列に対応する数が同じ（２つの行列が同じ）であれば "0" を、$matrix1 に対応する数が $matrix2 に対応する数よりも大きければ "1" を返す。
この比較は代数的なことは何も行わず、勝手な順序の関係であることに注意すること。
行列の配列により示された勝手な順序を提供するためだけの意図しかない。（２項探索を用いて）高速に特定の行列が既に生成されたか否かを確認するために用いられる。
これらは全て 上記 "cmp" 演算子から導出される。それぞれ "cmp" 演算子 の替わりに比較のための特定の型で用いることができる。
たとえば ($matrix1 le $matrix2) は (($matrix1 cmp $matrix2) <= 0) よりもよっぽど読みやすい！
Bit::Vector(3), Math::MatrixReal(3), DFA::Kleene(3), Math::Kleene(3), Set::IntegerFast(3), Set::IntegerRange(3).
本ドキュメントは Math::MatrixBool version 5.7 である。
Steffen Beyer, <sb@sdm.de>
Copyright (c) 1995, 1996, 1997, 1998, 1999 by Steffen Beyer. All rights reserved.
本パッケージはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。
|
|
Updated : 2008/01/14 |