Efficiently construct a square matrix with unique numbers in each row

Question

A matrix of size nxn needs to be constructed with the desired properties.

1. n is even. (given as input to the algorithm)
2. Matrix should contain integers from 0 to n-1
3. Main diagonal should contain only zeroes and matrix should be symmetric.
4. All numbers in each row should be different.

For various n , any one of the possible output is required.

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

Now the only idea that comes to my mind is to brute-force build combinations recursively and prune.

How can this be done in a iterative way perhaps efficiently?

Answer 1

IMO, You can handle your answer by an algorithm to handle this:

If 8x8 result is:

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

You have actually a matrix of two 4x4 matrices in below pattern:

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

And also each 4x4 is a matrix of two 2x2 matrices with a relation to a power of 2:

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

---

In other explanation I should say you have a 2x2 matrix of 0 and 1 then you expand it to a 4x4 matrix by replacing each cell with a new 2x2 matrix:

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

Now expand it again:

 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

---

I can calculate value of each cell by this C# sample code:

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