algorithm - 有效地构建每行具有唯一编号的方阵

需要使用所需的属性构造nxn大小的矩阵。

n是偶数。 (作为算法的输入)

矩阵应包含从0到n-1的整数

主对角线应仅包含零，并且矩阵应对称。

每行中的所有数字都应该不同。

对于各种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

现在，我想到的唯一想法是通过递归和修剪的方式强行构建组合。

如何以迭代的方式有效地做到这一点？

最佳答案

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);