Search code examples
arraysalgorithmmultiple-entries

Algorithm to get the entries of a table?


Say I have this table of non-negative entries:

    1   2   3   sum
1   4   5   1   10
2   6   12  7   25
3   0   3   14  17
4   7   2   5   14
sum 17  22  27  66

given:

  1. the number of columns C and number of rows R
  2. the two sums entries (the sum of each row and the sum of each column)
  3. and the total (66 in this example)

The goal is to produce the entries of the table (the inner cells; not the same ones. but, the sum must be equal to the given ones for each row and each column) all entries must be positive values.

Any pseudo code to do it?


Solution

  • Try my pseudo code. This rule named something like "Rule of North-West corner" (I unable find real name of this rule on wiki)

    row = 1
    col = 1
    
    while (col <= C && row <= R)
      Matrix[col, row] = Min(colsum[col], rowsum[row])
      colsum[col] = colsum[col] - Matrix[col, row]
      rowsum[row] = rowsum[row] - Matrix[col, row]
      while (col <= C && colsum[col] == 0) col++
      while (row <= R && rowsum[row] == 0) row++
    
    Print Matrix;