Effectively build a square matrix with unique numbers in each row

Question

A matrix of size nxn must be constructed with the required properties.

• n even. (defined as an input to the algorithm)
• Matrix must contain integers from 0 to n-1
• The main diagonal should contain only zeros, and the matrix should be symmetrical.
• All numbers on each line must be different.

For different n , any 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 combine assembly combinations with recursively and crop.

How can this be done in an iterative way, possibly efficiently?

Answer 1

IMO, you can process your answer using an algorithm to handle this:

If the result is 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 

You actually have a matrix of two 4x4 matrices in the following template:

 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 respect to degree 2:

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

---

In another explanation, I have to say that you have a 2x2 matrix 0 and 1 , then you expand it to a 4x4 matrix, 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 the value of each cell using this C # code example:

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

Answer 2

We know that every line should contain every number. Similarly, each line contains each number.

Take the CS convention of indices starting at 0.

First, consider how to put 1 in a matrix. Choose a random number k0, from 1 to n-1. Put 1 on line 0 to position (0, k0). In line 1, if k0 = 1, in this case there is already one. Otherwise, there are n-2 free positions and put 1 in position (1, k1). Continue this way until all 1 are placed. The last line has exactly one free position.

Next, repeat with 2, which should fit in the remaining places.

Now the problem is that we may not be able to completely fill the square. We may find that there are some limitations that make it impossible to fill in the last digits. The problem is that checking a partially filled Latin square is NP-complete. (wikipedia) This basically means pretty intensive computing and there isn't a single short algorithm. So I think the best thing you can do is create squares and check if they work or not.

If you only need one specific square for each n, then there may be simpler ways to generate them. Link Ted Hopp provided in his commentary on Latin Squares. A simple construction provides a way to generate a square starting with the addition of integers mod n.