各セル (または 0) に正の整数のみを持ち、各行と列の固定合計 (これらはアルゴリズム）。
例 : 行の合計が 2、1、列の合計が 0、1、2 のすべての 2x3 行列を列挙します。
| 0 0 2 | = 2
| 0 1 0 | = 1
0 1 2
| 0 1 1 | = 2
| 0 0 1 | = 1
0 1 2
これはかなり単純な例ですが、合計だけでなく N と M が増加するにつれて、多くの可能性が生じる可能性があります。
編集 1
アルゴリズムを開始するための有効な取り決めがあるかもしれません:
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
target_row_sum[i] は、行 i の予想される合計です。
上記の例では、2 番目の配置が示されています。
編集 2: ( j_random_hacker の最後のステートメントに基づく)
M を、指定された条件 (行と列の合計が固定、正または null のセル値) を検証する任意の行列とします。(a, b, c, d) を M の 4 つのセル値とします。ここで、(a, b) と (c, d) は同じ行にあり、(a, c) と (b, d) は同じ行にあります。桁。a を含むセルの行番号を Xa、列番号を Ya とします。
例：
| 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
初期条件を検証し、a、b、c、および d のみを変化させるすべての組み合わせを取得するアルゴリズムを次に示します。
// 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
次に、マトリックス値の可能なすべての組み合わせを見つけることができるはずです。
- 4 つのセルのすべての可能なグループの最初の行列にアルゴリズムを適用します。
- 親実行ですでに使用されているグループを除く、4 つのセルからなる考えられるすべてのグループに対して、前の反復によって取得された各サブマトリックスにアルゴリズムを再帰的に適用します。
再帰の深さは で(N*(N-1)/2)*(M*(M-1)/2)、実行ごとに((N*(N-1)/2)*(M*(M-1)/2) - depth)*(I+J+1)部分行列が生成されます。ただし、これにより多くの重複した行列が作成されるため、これはおそらく最適化される可能性があります。