StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POEnumerate matrix combinations with fixed row and column sums
text
Body
copied!<p>I'm attempting to find an algorithm (not a matlab command) to enumerate all possible NxM matrices with the constraints of having only positive integers in each cell (or 0) and fixed sums for each row and column (these are the parameters of the algorithm).</p> <p>Exemple : Enumerate all 2x3 matrices with row totals 2, 1 and column totals 0, 1, 2:</p> <pre><code>| 0 0 2 | = 2 | 0 1 0 | = 1 0 1 2 | 0 1 1 | = 2 | 0 0 1 | = 1 0 1 2 </code></pre> <p>This is a rather simple example, but as N and M increase, as well as the sums, there can be a lot of possibilities.</p> <hr> <p>Edit 1</p> <p>I might have a valid arrangement to start the algorithm:</p> <pre><code>matrix = new Matrix(N, M) // NxM matrix filled with 0s FOR i FROM 0 TO matrix.rows().count() FOR j FROM 0 TO matrix.columns().count() a = target_row_sum[i] - matrix.rows[i].sum() b = target_column_sum[j] - matrix.columns[j].sum() matrix[i, j] = min(a, b) END FOR END FOR </code></pre> <p>target_row_sum[i] being the expected sum on row i.</p> <p>In the example above it gives the 2nd arrangement.</p> <hr> <p>Edit 2: (based on <a href="https://stackoverflow.com/a/17885398/547733">j_random_hacker's last statement</a>)</p> <p>Let M be any matrix verifying the given conditions (row and column sums fixed, positive or null cell values). Let (a, b, c, d) be 4 cell values in M where (a, b) and (c, d) are on the same row, and (a, c) and (b, d) are on the same column. Let Xa be the row number of the cell containing a and Ya be its column number.</p> <p>Example:</p> <pre><code>| 1 a b | | 1 2 3 | | 1 c d | -> Xa = 0, Ya = 1 -> Xb = 0, Yb = 2 -> Xc = 2, Yc = 1 -> Xd = 2, Yd = 2 </code></pre> <p>Here is an algorithm to get all the combinations verifying the initial conditions and making only a, b, c and d varying:</p> <pre><code>// A matrix array containing a single element, M // It will be filled with all possible combinations matrices = [M] I = min(a, d) J = min(b, c) FOR i FROM 1 TO I tmp_matrix = M tmp_matrix[Xa, Ya] = a - i tmp_matrix[Xb, Yb] = b + i tmp_matrix[Xc, Yc] = c - i tmp_matrix[Xd, Yd] = d + i matrices.add(tmp_matrix) END FOR FOR j FROM 1 TO J tmp_matrix = M tmp_matrix[Xa, Ya] = a + j tmp_matrix[Xb, Yb] = b - j tmp_matrix[Xc, Yc] = c + j tmp_matrix[Xd, Yd] = d - j matrices.add(tmp_matrix) END FOR </code></pre> <p>It should then be possible to find every possible combination of matrix values:</p> <ol> <li>Apply the algorithm on the first matrix for every possible group of 4 cells ;</li> <li>Recursively apply the algorithm on each sub-matrix obtained by the previous iteration, for every possible group of 4 cells except any group already used in a parent execution ;</li> </ol> <p>The recursive depth should be <code>(N*(N-1)/2)*(M*(M-1)/2)</code>, each execution resulting in <code>((N*(N-1)/2)*(M*(M-1)/2) - depth)*(I+J+1)</code> sub-matrices. But this creates a LOT of duplicate matrices, so this could probably be optimized.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload