Algorithm::RandomMatrixGeneration - Perl module to generate matrix given the marginals.

Location : Home > Languages > Perl > Package
Title : Algorithm::RandomMatrixGeneration

　Algorithm::RandomMatrixGeneration - 所与の周辺和を満たす乱数行列を生成

use Algorithm::RandomMatrixGeneration;

my @result = generateMatrix(\@row_marginals, \@col_marginals);

　周辺和が負の整数値を取る例

use Algorithm::RandomMatrixGeneration;

my @rmar = ('-5','5','-3');
my @cmar = ('2','3','-2','-6');
my @result = generateMatrix(\@rmargs, \@cmargs, "-");

　出力の行列は以下の通りである。

0 -1 1 3 2 -5 3 -2
0 5
0 -2 2 3 3 -4

　周辺和が正の実数値を取る例

use Algorithm::RandomMatrixGeneration;

my @rmargs = (13.01,11,13,13,12,13);
my @cmargs = (23.005,32.005,10,10);
my @result = generateMatrix(\@rmargs, \@cmargs, 3);

　出力の行列は以下の通りである。

0 2.694  1 9.665  2 0.393  3 0.258
0 6.539  1 0.910  2 2.209  3 1.342
0 8.469  1 3.565  2 0.839  3 0.127
0 2.719  1 2.748  2 0.604  3 6.929
0 0.946  1 3.771  2 5.939  3 1.344
0 1.638  1 11.346  2 0.016

インプット

　generateMatrix 関数は４つのパラメータをとる。

行和（row marginals）を含む１次元配列（実数または整数）
列和（column marginals）を含む１次元配列（実数または整数）
精度（Precision）：整数の場合は " - " を指定。実数の場合は生成される行列の要素の精度（推奨される精度は 4 ）。
種（Seed）：乱数生成のための種。（デフォルトはなし。オプションのパラメータである。）

アウトプット

　generateMatrix 関数は生成した乱数行列を含む２次元配列を返す。
　生成された行列はこの返り値の行列に疎な形で格納されている。つまりこの行列の非零値のみが格納されている。したがって返り値の行列は以下のようにして処理する。

for(my $row=0; $i<=$num_rows; $i++){
   for(my $col=0; $j<=$num_cols; $j++){
      if(defined $returned_matrix[$row][$col]){
         print "$col $returned_matrix[$row][$col]  ";
      }
   }
   print "\n";
}

説明

　本モジュールは所与の行和及び列和（周辺和）を満たすような乱数を生成する。
　周辺和が実数値であれば各要素の値も実数である。周辺和が整数であれば各要素の値も整数である。周辺和が負であれば要素のうちにいくつかまたは全部が負の値となる。

詳細

　たとえば以下のような周辺和が与えられているとすると、これを満たすように本モジュールは機能し、 x の値を埋めていく。

x    x    x    x    x    |  3
x    x    x    x    x    |  2
x    x    x    x    x    |  3
x    x    x    x    x    |  2
------------------------------
2    2    2    2    2    |  10

　アルゴリズムは以下のようなものである。

For 各セル（行を順になぞる）

以下に示すアルゴリズムで乱数を生成する。

生成された値を列和・行和から引く。

End for. Done.

　乱数生成アルゴリズムは以下の通りである。

for each cell C(i,j)
{
   # 乱数生成の範囲 (min, max) を求める。
   max = MIN(row_marg[i], col_marg[j])

   # 最大値が０でなければ最小値を決定する。
   # 最小値を決定するために全列に対し現在の列を超えた
   #  col_marginals の和を求める。この和は行和を満たし
   # ているが現在の列和を満たしていない。
   # 乱数の下限を計算するためにこの和から row_marginal 
   # を引く。この下限を設定しなければこの下限よりも小
   # さな値が生成され、他の row_marginal 及び column marginals 
   # が不可能になる状況が生まれるためである。

   if(max != 0)
   {
      2_term = 0
      for each col k > j
      {
          2_term = 2_term + col_marg[k]
      }
      min = row_marg[i] - 2_term
      if(marginals positive)
      {
        	if(min < 0)
        	{
            	min = 0
        	}
		}
    }
    else
    {
        min = max = 0   # 最大値が０なら最小値も０
    }

    # 範囲内で乱数を生成
    random_num = rand(min, max)
}

例：

Cell 0:
max = MIN(3,2) = 2
2_term = 2 + 2 + 2 + 2 = 8
min = 3 - 8 = -5
therefore: min = 0
(min, max) = (0,2) = 0
0    x    x    x    x    |  3
x    x    x    x    x    |  2
x    x    x    x    x    |  3
x    x    x    x    x    |  2
----------------------------------------------
2    2    2    2    2    |

Cell 1:
max = MIN(3,2) = 2
2_term = 2 + 2 + 2 = 6
min = 3 - 6 = -3
therefore: min = 0
(min, max) = (0,2) = 0
0    0    x    x    x    |  3
x    x    x    x    x    |  2
x    x    x    x    x    |  3
x    x    x    x    x    |  2
----------------------------------------------
2    2    2    2    2    |

Cell 2:
max = MIN(3,2) = 2
2_term = 2 + 2 = 4
min = 3 - 4 = -1
therefore: min = 0
(min, max) = (0,2) = 0
0    0    0    x    x    |  3
x    x    x    x    x    |  2
x    x    x    x    x    |  3
x    x    x    x    x    |  2
----------------------------------------------
2    2    2    2    2    |

Cell 3:
max = MIN(3,2) = 2
2_term = 2
min = 3 - 2 = 1
(min, max) = (1,2) = 1
0    0    0    1    x    |  2
x    x    x    x    x    |  2
x    x    x    x    x    |  3
x    x    x    x    x    |  2
----------------------------------------------
2    2    2    1    2    |

Cell 4:
max = MIN(2,2) = 2
2_term = 0
min = 2 - 0 = 2
(min, max) = (2,2) = 2
0    0    0    1    2    |  0
x    x    x    x    x    |  2
x    x    x    x    x    |  3
x    x    x    x    x    |  2
----------------------------------------------
2    2    2    1    0    |

Cell 5:
max = MIN(2,2) = 2
2_term = 2 + 2 + 1 + 0 = 5
min = 3 - 5 = -2
therefore, min = 0
(min, max) = (0,2) = 1
0    0    0    1    2    |  0
1    x    x    x    x    |  1
x    x    x    x    x    |  3
x    x    x    x    x    |  2
----------------------------------------------
1    2    2    1    0    |

Cell 6:
max = MIN(1,2) = 1
2_term = 2 + 1 + 0 = 3
min = 1 - 3 = -2
therefore, min = 0
(min, max) = (0,1) = 0
0    0    0    1    2    |  0
1    0    x    x    x    |  1
x    x    x    x    x    |  3
x    x    x    x    x    |  2
----------------------------------------------
1    2    2    1    0    |

Cell 7:
max = MIN(1,2) = 1
2_term = 1 + 0 = 1
min = 1 - 1 = 0
(min, max) = (0,1) = 1
0    0    0    1    2    |  0
1    0    1    x    x    |  0
x    x    x    x    x    |  3
x    x    x    x    x    |  2
----------------------------------------------
1    2    1    1    0    |

Cell 8:
max = MIN(0,1) = 0
min = 0
(min, max) = (0,0) = 0
0    0    0    1    2    |  0
1    0    1    0    x    |  0
x    x    x    x    x    |  3
x    x    x    x    x    |  2
----------------------------------------------
1    2    1    1    0    |

Cell 9:
max = MIN(0,0) = 0
min = 0
(min, max) = (0,0) = 0
0    0    0    1    2    |  0
1    0    1    0    0    |  0
x    x    x    x    x    |  3
x    x    x    x    x    |  2
----------------------------------------------
1    2    1    1    0    |

Cell 10:
max = MIN(3,1) = 1
2_term = 2 + 1 + 1 + 0 = 4
min = 3 - 4 = -1
therefore, min = 0
(min, max) = (0,1) = 1
0    0    0    1    2    |  0
1    0    1    0    0    |  0
1    x    x    x    x    |  2
x    x    x    x    x    |  2
----------------------------------------------
0    2    1    1    0    |

Cell 11:
max = MIN(2,2) = 2
2_term = 1 + 1 + 0 = 2
min = 2 - 2 = 0
(min, max) = (0,2) = 0
0    0    0    1    2    |  0
1    0    1    0    0    |  0
1    0    x    x    x    |  2
x    x    x    x    x    |  2
----------------------------------------------
0    2    1    1    0    |

Cell 12:
max = MIN(2,1) = 1
2_term = 1 + 0 = 1
min = 2 - 1 = 1
(min, max) = (1,1) = 1
0    0    0    1    2    |  0
1    0    1    0    0    |  0
1    0    1    x    x    |  1
x    x    x    x    x    |  2
----------------------------------------------
0    2    0    1    0    |

Cell 13:
max = MIN(1,1) = 1
2_term = 0 = 0
min = 1 - 0 = 1
(min, max) = (1,1) = 1
0    0    0    1    2    |  0
1    0    1    0    0    |  0
1    0    1    1    x    |  0
x    x    x    x    x    |  2
----------------------------------------------
0    2    0    0    0    |

Cell 14:
max = MIN(0,0) = 0
min = 0
(min, max) = (0,0) = 0
0    0    0    1    2    |  0
1    0    1    0    0    |  0
1    0    1    1    0    |  0
x    x    x    x    x    |  2
----------------------------------------------
0    2    0    0    0    |

Cell 15:
max = MIN(2,0) = 0
min = 0
(min, max) = (0,0) = 0
0    0    0    1    2    |  0
1    0    1    0    0    |  0
1    0    1    1    0    |  0
0    x    x    x    x    |  2
----------------------------------------------
0    2    0    0    0    |

Cell 16:
max = MIN(2,2) = 2
2_term = 0 + ... = 0
min = 2 - 0 = 2
(min, max) = (2,2) = 2
0    0    0    1    2    |  0
1    0    1    0    0    |  0
1    0    1    1    0    |  0
0    2    x    x    x    |  0
----------------------------------------------
0    0    0    0    0    |

Cell 17:
max = MIN(0,0) = 0
min = 0
(min, max) = (0,0) = 0
0    0    0    1    2    |  0
1    0    1    0    0    |  0
1    0    1    1    0    |  0
0    2    0    x    x    |  0
----------------------------------------------
0    0    0    0    0    |

Cell 18:
max = MIN(0,0) = 0
min = 0
(min, max) = (0,0) = 0
0    0    0    1    2    |  0
1    0    1    0    0    |  0
1    0    1    1    0    |  0
0    2    0    0    x    |  0
----------------------------------------------
0    0    0    0    0    |

Cell 19:
max = MIN(0,0) = 0
min = 0
(min, max) = (0,0) = 0
0    0    0    1    2    |  0
1    0    1    0    0    |  0
1    0    1    1    0    |  0
0    2    0    0    0    |  0
----------------------------------------------
0    0    0    0    0    |

Done!!

エクスポート

generateMatrix

著者

　Anagha Kulkarni, <kulka020@d.umn.edu>
　Ted Pedersen, <tpederse@d.umn.edu>

著作権とライセンス

　本プログラムはフリーソフトウェアであり、Free Software Foundation により公開された GNU General Public License （version 2 またはユーザの考えに基づきそれ以降のバージョン）の条件の下で修正／再配布してもよい。
　本プログラムは有用であると考え配布されているが、 MERCHANTABILITY または FITNESS FOR A PARTICULAR PURPOSE で保証されていたとしても無保証である。詳しくは GNU General Public License を参照のこと。
　本プログラムに関しては GNU General Public License のコピーを入手すべきである。もし手元になければ the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. まで連絡を。

Updated : 2007/05/08