合計からの行列再構成

Question

すべての行と列の合計が与えられたすべての正の整数要素を持つ行列を再構築したい。

a0 a1 a2 .. aN | Σa 
b0 b1 b2 .. bN | Σb 
.. . . . .. | .. 
.. . . . .. | .. 
z0 z1 z2 .. zN | Σz 
---------------+---- 
Σ0 Σ1 Σ2 .. ΣN | 

行と列の和所与全て可能行列要素の組み合わせを見つけるアルゴリズムがあります。

参考までにお待ちください。

Answer 1

はい。あなたが持っているものは、system of linear equationsです。各行に1つと、各列に1つあります。 m * n個の変数とm + n個の式。

このようなシステムを解決するソリューションのセットを計算（および表現）する方法は、環境によって異なります。

EDIT：が表示されます。この問題の大きな例については、integer programmingを参照してください。

しかし、youre行列と行/列合計が小さい場合は、すべての解をbacktrackingで見つけることができます。非常に高レベルの擬似コード：線形方程式の結果のシステムは、行列のエントリは（おそらく「非ネガティブ」実際に意味するところ）ポジティブであることを確認してくださいどのよう

function SOLVE(partially filled M) { 

    if (M has no empty entries) { 

     M is a solution 

    } else { 

     ij <- one empty position of M 
     // in practice, try picking one that reduces the number of 
     // iterations of the following loop 

     for (each possible value v of M[ij], subject to the constraints) { 
      M' <- a copy of M 
      M'[ij] = v 
      SOLVE(M') 
    } 
} 


M0 <- an empty Matrix of correct size 

SOLVE(M0)