Matrixrekonstruktion aus Summen

Question

Ich möchte eine Matrix mit allen positiven ganzzahligen Elementen rekonstruieren, die die Summe jeder Zeile und Spalte angibt.

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

Gibt es einen Algorithmus, die alle möglich Matrixelementkombinationen, da die Zeilen- und Spaltensummen finden.

Jede Referenz wird sehr geschätzt.

Answer 1

Ja. Was Sie haben, ist eine system of linear equations, eine für jede Zeile und eine für jede Spalte; m * n Variablen und m + n Gleichungen.

Wie zu berechnen (und darzustellen) die Menge der Lösungen zu lösen ein solches System hängt davon ab, was Ihre Umgebung ist.

EDIT: Ich sehe. Für große Fälle dieses Problems, siehe integer programming.

Aber wenn Ihre Matrix und Zeile/Spalte Summe klein sind, wird es möglich sein, alle Lösungen von backtracking zu finden. Sehr hoher Pseudocode:

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)