algorithm - 有效地构造一个方阵，每行都有唯一的数字

Question

需要构造具有所需属性的大小为 nxn 的矩阵。

1. n 是偶数。 (作为算法的输入)
2. 矩阵应包含从 0 到 n-1
的整数
3. 主对角线应仅包含零且矩阵应对称。
4. 每行中的所有数字都应该不同。

对于各种 n ，可能的输出中的任何一个都是必需的。

input
2
output
0 1
1 0

input
4
output
0 1 3 2
1 0 2 3
3 2 0 1
2 3 1 0

现在我想到的唯一想法是递归地暴力构建组合并修剪。

如何以迭代的方式高效地完成这项工作？

Answer 1

IMO，您可以通过算法来处理您的答案:

如果 8x8 结果是:

0 1 2 3 4 5 6 7 
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0

您实际上有一个由两个 4x4 矩阵组成的矩阵，格式如下:

m0 => 0 1 2 3   m1 => 4 5 6 7     pattern => m0 m1
      1 0 3 2         5 4 7 6                m1 m0
      2 3 0 1         6 7 4 5
      3 2 1 0         7 6 5 4

而且每个 4x4 都是两个 2x2 矩阵的矩阵，它们与 2 的幂有关系:

m0 => 0 1       m1 => 2 3         pattern => m0 m1
      1 0             3 2                    m1 m0

---

在其他解释中我应该说你有一个 2x2 矩阵 0 和 1 然后你将它扩展到 4x4 矩阵，方法是用新的 2x2 矩阵替换每个单元格:

0 => 0+2*0 1+2*0    1=> 0+2*1 1+2*1
     1+2*0 0+2*0        1+2*1 0+2*1

result => 0 1 2 3
          1 0 3 2
          2 3 0 1
          3 2 1 0

现在再次展开它:

 0,1=> as above  2=> 0+2*2 1+2*2   3=> 0+2*3 1+2*3
                     1+2*2 0+2*2       1+2*3 0+2*3

---

我可以通过这个 C# 示例代码计算每个单元格的值:

// i: row, j: column, n: matrix dimension
var v = 0;
var m = 2;
do
{
    var p = m/2;
    v = v*2 + (i%(n/p) < n/m == j%(n/p) < n/m ? 0 : 1);
    m *= 2;

} while (m <= n);