3

我有两个十进制数变量 colSum 和 rowSum，使用我想基于这些总和构建二进制值矩阵的变量，rowSum 数组变量是每行添加所有 1 的结果，colSum 数组也是如此。

所以，如果你有

rowSum = [0,1,2]
colSum = [1,1,1]

您将必须正确构建以下数组

matrix = [
 [0,0,0],
 [0,0,1],
 [1,1,0]
]

我在 PHP 中使用这种方法，它适用于 3x3 矩阵，但不适用于更大的矩阵，例如 8x8。首先，使用 rowSum 值填充行中的所有 1。然后，尝试找到 2 列的错误总和值，并在同一行中将它们（1 与 cero 值）互换，直到我得到正确的 colSum 值。但这不起作用，因为我需要对标准进行一些控制来更改同一行中两列的 1 和 0 ......

这是我正在使用的方法。

假设我们有这个矩阵（N=3 -> NxN）：

0  0  0
0  0  1
1  1  0

那么我们有以下数组

R0 = {0,1,2} //--> result of sums of each rows: ( 0+0+0, 0+0+1 , 1+1+0 )
C0 = {1,1,1} // ->sums of each columns

步骤1

在每行中使用与 R0(i) 一样多的 1 创建并填充 NxN 数组：

0  0  0
1  0  0
1  1  0

现在计算这个新矩阵的总和：R1 = {0,1,2} C1 = {2,1,0}

第2步

检查创建的矩阵的列总和的所有元素是否与 C0 (origin) 具有相同的值

for ( i=0, N-1) do

 if C0(i)!=C1(i) then
   ReplaceColumn(i)
 end

end

要替换列，我们必须深入研究条件。C0(0) = 1 != C1(0) = 2 第一列总和确实满足调用替换的条件，所以

第 3 步

选择应用分支和绑定方法的标准，并找到最佳行来更改满足全局条件的列（所有列总和）。

列总和之间差异的变化量为：

|C0(i)-C1(i)|

对于此示例，|C0(0)-C1(0)| = 1 变化。如果更改在列的总和之间产生更大的差异，则返回条件必须是。

Σi,N(|C0(i)-C1(i)|)

那么，这种方法真的可行吗？

4

1 回答 1

1

目标是构造满足行列和的矩阵还是满足它们的矩阵？从问题中不清楚，但如果是前者（“ the ”案例），那么这是不可能的。

假设您可以以这种方式唯一地表示任何 m × m 位矩阵。然后考虑以下假设的压缩算法。

  • 取 2 2n位数据
  • 将其视为 2 n × 2 n位
  • 为了描述数据，使用 2 × 2 n行和列总和，每个使用最多 log 2 (2 n ) = n 位
  • 数据被压缩为 2 × n × 2 n位

由于 2 × n × 2 n << 2 2n并且这个过程可以不断重复，因此您可以仅通过行和列和来唯一表示任何 m × m 位矩阵的假设是错误的。

于 2015-01-20T20:12:36.177 回答