CODEWITHSUNDEEP
algorithmmathmatrixlinear-algebrasymmetric
A. Sam
A. Sam

Reputation: 893

Efficiently construct a square matrix with unique numbers in each row

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?

Upvotes: 7

Views: 1065

Answers (3)

Yauhen Yakimovich
Yauhen Yakimovich

Reputation: 14211

I might be wrong, but if you just look for printing a symmetric table - a special case of latin squares isomorphic to the symmetric difference operation table over a powerset({0,1,..,n}) mapped to a ring {0,1,2,..,2^n-1}.

One can also produce such a table, using XOR(i,j) where i and j are n*n table indexes.

For example: 

def latin_powerset(n):
    for i in range(n):
        for j in range(n):
            yield (i, j, i^j)

Printing tuples coming from previously defined special-case generator of symmetric latin squares declared above:

def print_latin_square(sq, n=None):
    cells = [c for c in sq]
    if n is None:
        # find the length of the square side
        n = 1; n2 = len(cells)
        while n2 != n*n:
            n += 1
    rows = list()
    for i in range(n):
        rows.append(" ".join("{0}".format(cells[i*n + j][2]) for j in range(n)))
    print("\n".join(rows))

square = latin_powerset(8)
print(print_latin_square(square))

outputs:

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

See also

This covers more generic cases of latin squares, rather than that super symmetrical case with the trivial code above:

Upvotes: 0

shA.t
shA.t

Reputation: 16958

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

Upvotes: 3

Salix alba
Salix alba

Reputation: 7824

We know each row must contain each number. Likewise, each row contains each number.

Let us take CS convention of indices starting from 0.

First, consider how to place the 1's in the matrix. Choose a random number k0, from 1 to n-1. Place the 1 in row 0 at position (0,k0). In row 1, if k0 = 1 in which case there is already a one placed. Otherwise, there are n-2 free positions and place the 1 at position (1,k1). Continue in this way until all the 1 are placed. In the final row there is exactly one free position.

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

Now the problem is that we might not be able to actually complete the square. We may find there are some constraints which 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 compute intensive and there no know short-cut algorithm. So I think the best you can do is generate squares and test if they work or not.

If you only want one particular square for each n then there might be simpler ways of generating them. The link Ted Hopp gave in his comment Latin Squares. Simple Construction does provide a method for generating a square starting with the addition of integers mod n.

Upvotes: 0

Related Questions