行と列の合計が指定された値になるように、すべての非負の整数K行K行列を列挙するアルゴリズムを探しています。
正確に言うと、K負でない整数の-ベクトルが与えられた場合、、を使用して、およびのようなすべての行列を探します。mnsum(m) = sum(n)X=(x_{ij})sum(x_{ij},i=1,...,K) = m_jsum(x_{ij},j=1,...,K) = n_i
したがって、各行はの対応する要素の整数分割でありn、各列はの対応する要素の整数分割ですm。
コメントから、実装やいくつかの文献を見つけるために問題の名前を探していることがわかります。したがって、問題名は「固定マージンで分割表を列挙する」であり、実際には非常に複雑です（2行2列の場合を除く）。2行n列しかない場合でも、＃P-completeであることが知られています。したがって、通常、近似アルゴリズムを使用して解をカウントします（またはmcmcアルゴリズムを使用してランダムに生成します）。不思議なことに、D.KnuthとF.Ruskeyの両方が、それぞれの本の演習として問題を残しています。
このホワイトペーパーでは、正確で近似的なアルゴリズムの優れた（最新ではない）レビューを提供します。典型的なアプリケーションは、フィッシャーの直接確率検定を計算するための統計にあるため、これを検索しても良い結果が得られます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加