How to build a matrix N * (N + 1) with a number in the range 1 ~ N * N and fully distributed?

Question

Suppose that a matrix with N + 1 rows was created for a given number N, and each row has N columns, each column has an N number in the range [1, N ^ 2]. And the matrix has this function: each column has a number N, the numbers are completely distributed on another row.

Sorry for the fact that English is not my native language; I tried my best to clearly describe the problem. If you have a better description of this problem, please teach me how to do it.

For example, N = 3, I can build a matrix that has 4 rows and 3 columns, and the number [1, 3 ^ 2]. matrix:

[1, 2, 3], [4, 5, 6], [7, 8, 9] [1, 4, 7], [2, 5, 8], [3, 6, 9] [1, 5, 9], [2, 6, 7], [3, 4, 8] [1, 6, 8], [2, 4, 9], [3, 5, 7] 

In this example, each row has 3 columns, each column has 3 numbers, and 3 numbers are allocated in 3 different columns in each other row. The following is an example of the second row of the 2nd row ([2,5,8]). Three numbers [2,5,8] are in different columns in other lines. No other column has [2.5] , [5.8] or [2.8] , but each column of the other rows has and has only one of them.

[1, 2 , 3], [4, 5 , 6], [7, 8 , 9]

[1, 4, 7], [ 2 , 5 , 8 ], [3, 6, 9]

[1, 5 , 9], [ 2 , 6, 7], [3, 4, 8 ]

[1, 6, 8 ], [ 2 , 4, 9], [3, 5 , 7]

I found a quick way to build such a matrix when N is a prime.

But when N is not a prime, I can only find an exhaustive method. But this is the O ((N ^ (N-1) ^ N) algorithm. I can build the matrix in 5 seconds when N is 4, but I have to take 328 days when N is 5.

This is what I create when N = 4:

 [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16] [1, 5, 9, 13], [2, 6, 10, 14], [3, 7, 11, 15], [4, 8, 12, 16] [1, 6, 11, 16], [2, 5, 12, 15], [3, 8, 9, 14], [4, 7, 10, 13] [1, 7, 12, 14], [2, 8, 11, 13], [3, 5, 10, 16], [4, 6, 9, 15] [1, 8, 10, 15], [2, 7, 9, 16], [3, 6, 12, 13], [4, 5, 11, 14] 

I want to learn how to build a matrix with N = 100 or another large number. Can anyone solve this problem?

The following is a way to construct a matrix when N is a prime. Use also an example.

For example, N = 3:

• The first line is always continuous: [1,2,3],[4,5,6],[7,8,9]
• For the next lines, I select the number from the first line with a different offset.

Below is my code on how to generate a matrix when N is prime. But I thought that there should be another way to generate the matrix when N is not simple.

 #!/bin/env python def main(n): data = [] for i in range(0, n): data.append([n*i + x for x in range(0, n)]) print data # the first row offset = 0 while offset < n: row = [] for i in range(0, n): idx = i grid = [] for j in range(0, n): grid.append(data[j][idx%n]) idx += offset # every row I use a different step. It works for prime. row.append(grid) print row offset += 1 if __name__ == '__main__': main(7) 

Answer 1

Short answer: this is a well-known and studied problem in the field of combinatorics, and (not wanting to hinder you), it seems very difficult to solve computationally. For N simple or simple power, it’s easy to generate examples as soon as you know how to do it. For N=6 or N=10 it is known that there are no solutions. For many other N (for example, N=12 , N=15 , etc.) People searched, but no one knows if there are solutions at all.

Longer answer: what you describe corresponds to a finite affine plane . This is a finite set of “points” together with a finite set of “lines” (which for simplicity we can consider as subsets of the set of points) that satisfy the following axioms:

• For any two points, there is a unique string containing these two points.
• For any line L and any point P not on L, there exists a unique line M parallel to L and passing (i.e., containing) P. (Here M and L are considered parallel if they do not have common points - i.e. they are not intersect.)
• There is a 4-point configuration here, so the three columns are not collinear.

To suit your example: in the case of 3x3, your “dots” are numbers 1 through 9. Your “rows” are “columns”, and each row in your configuration gives you a set of mutually parallel rows.

Axiom 1 above roughly corresponds to your "fully distributed" property; axiom 2 is what allows you to organize your “columns” into rows so that each row contains each number exactly once. Axiom 3 is not so interesting: it is a non-degeneracy condition designed to exclude degenerate configurations allowed for the first two axioms, but otherwise not having much in common with non-degenerate cases.

If you start the search, you will find many results for finite projective planes , but less for finite affine planes. This is because any affine plane can easily be completed to the projective plane by adding a line of infinite points. Conversely, for a given finite projective plane, you can delete the line and all points on it to get an affine plane. Therefore, if you can create finite projective planes, you can create finite affine planes and vice versa.

Here is an example of this completion process, starting with the affine plane that you have for N=3 . You had:

 [1, 2, 3], [4, 5, 6], [7, 8, 9] [1, 4, 7], [2, 5, 8], [3, 6, 9] [1, 5, 9], [2, 6, 7], [3, 4, 8] [1, 6, 8], [2, 4, 9], [3, 5, 7] 

Add four new points ("points at infinity"), which we will call "A", "B", "C" and "D". Each current line gets a new point (one of these points at infinity) added to it, and we also get one new line consisting of these new points at infinity. Note that any two lines that were previously parallel (i.e., were on the same line above) were completed with the same point at infinity, so now we have a very specific meaning for the often heard phrase: “Two parallel lines meet at infinity. " The new structure is as follows:

 [1, 2, 3, A], [4, 5, 6, A], [7, 8, 9, A] [1, 4, 7, B], [2, 5, 8, B], [3, 6, 9, B] [1, 5, 9, C], [2, 6, 7, C], [3, 4, 8, C] [1, 6, 8, D], [2, 4, 9, D], [3, 5, 7, D] [A, B, C, D] 

So now we have 13 points and 13 lines, so for each pair of different points there is a single line through these two points, and for each pair of separate lines these lines intersect at exactly one point. And this beautifully symmetric situation largely coincides with the finite projective plane (modulo another non-degeneracy condition). In this case, we just described a finite projective plane (unique up to isomorphism) of order 3 .

Here are some well-known facts about finite projective planes of order N (where N here exactly matches your N ):

• if N is a simple or simple degree, then there exists a finite projective plane of order N ; this can be created directly and simply from a finite field of order N , which is what your algorithm does when N is simple
• there are also finite projective planes that do not arise in this way: the so-called non-Sarguan planes. There are three known non-Desarguan planes of order 9 , for example
• there are no final projective planes of orders 6 or 10 (the latter was confirmed by computer search, which took about 2000 hours of supercomputer time in the late 1980s)
• it is not known whether there exists a finite projective plane of order 12 (although she suggested that it does not exist)
• there is no known finite projective plane whose order is neither simple nor simple degree
• some orders (including n=14 ) can be excluded directly through the Brook-Reiser-Chaulla theorem

Here is some code that directly builds the solution for N=4 as an affine plane over a finite four-element field, which I will call GF4 . First we need an implementation of this field. One of the following is perhaps unnecessarily unobvious and was chosen for simplicity of the multiplication operation.

 class GF4: """ A quick and dirty implementation of the finite field (Galois field) of order 4. Elements are GF4(0), GF4(1), GF4(8), GF4(9). This representation was chosen for the simplicity of implementation of multiplication. """ def __init__(self, bits): self.bits = bits def __add__(self, other): return GF4(self.bits ^ other.bits) __sub__ = __add__ # because we're in characteristic 2 def __mul__(self, other): return GF4(self.bits * other.bits % 55 & 9) def __eq__(self, other): return self.bits == other.bits def __hash__(self): return hash(self.bits) 

Now we will build scalars over the field, then use them to create first the totality of all points on the plane (only pairs of scalars), and then the totality of all lines in the plane (by listing the pairs of points):

 # Our scalars are all four elements of GF4. scalars = list(map(GF4, [0, 1, 8, 9])) # Points are simply pairs of scalars points = [(x, y) for x in scalars for y in scalars] # Every pair of nonequal points determines a line. def line_through(p, q): """ Return a frozenset of all the points on the line through p and q. """ # We want our lines to be hashable, so use a frozenset. return frozenset( (p[0] + t*(q[0] - p[0]), p[1] + t*(q[1] - p[1])) for t in scalars ) # Create all lines; every line is created multiple times, so use # a set to get unique lines. lines = {line_through(p, q) for p in points for q in points if p != q} 

Our points at present are pairs of objects of type GF4 ; to show compliance with your problem, we want to redo those by replacing the points with integers 1 to 16 :

 relabel = dict(zip(points, range(1, 17))) lines = [sorted(map(relabel.get, line)) for line in lines] 

Now we can print the lines one by one, but to get your lines, we also need to group the lines into mutually parallel groups:

 def parallel(l, m): """Return True if l and m are parallel, else False.""" return not(set(l) & set(m)) rows = [] while lines: l = lines.pop() parallel_to_l = {m for m in lines if parallel(m, l)} lines -= parallel_to_l rows.append(sorted({l} | parallel_to_l)) 

And now we can print the results, sorting for convenience:

 for row in sorted(rows): print(row) 

Here is the conclusion; it is essentially identical to the calculated output.

 [(1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16)] [(1, 5, 9, 13), (2, 6, 10, 14), (3, 7, 11, 15), (4, 8, 12, 16)] [(1, 6, 11, 16), (2, 5, 12, 15), (3, 8, 9, 14), (4, 7, 10, 13)] [(1, 7, 12, 14), (2, 8, 11, 13), (3, 5, 10, 16), (4, 6, 9, 15)] [(1, 8, 10, 15), (2, 7, 9, 16), (3, 6, 12, 13), (4, 5, 11, 14)]