如何建立一个N*(N + 1)矩阵,其数量范围为1~N*N并且是完全分布的？

Question

假设对于给定数量N,生成具有N + 1行的矩阵,并且每行具有N列,每列在范围[1,N ^ 2]中具有N个数.矩阵具有此功能:每列都有N个数字,数字完全分布在另一行.

对不起,英语不是我的母语,我尽力清楚地描述问题,如果你有更好的描述这个问题,请教我如何.

例如N = 3,我可以构建一个矩阵,它有4行3列,数字为[1,3 ^ 2].矩阵是:

[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]

在此示例中,每行有3列,每列有3个数字,3个数字分布在每隔一行的3个不同列中.以下是使用第2行第2列([2,5,8])作为例子.三个数字[2,5,8]在其他行的不同列中.没有其他任何列具有[2,5],[5,8]或[2,8],但其他行中的每列都只有一个列.

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

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

[ 51,9],[ 2,6,7],[3,4 8],

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

当N是素数时,我找到了一种快速构建矩阵的方法.

但是当N不是素数时,我只能找到一种详尽的方法.但它是一个O((N ^(N-1)^ N)算法.当N为4时,我可以在5秒内构建一个矩阵,但是当N为5时我应该花费328天.

这是我在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]

我想找出如何构建N = 100或更大数字的矩阵.有人能解决这个问题吗？

以下是当N为素数时我如何构建矩阵.也用例子.

例如N = 3:

1. 第一行总是连续的: [1,2,3],[4,5,6],[7,8,9]
2. 对于以下行,我从第一行中选择一个具有不同偏移量的数字.

以下是我在N为素数时如何生成矩阵的代码.但我认为当N不是素数时,必须有其他方法来生成矩阵.

#!/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

简短的回答:这是组合学领域中已知和研究的问题,并且(不想劝阻你)似乎很难在计算上解决.对于N素数或素数,一旦你知道如何,很容易生成例子.对于N=6或者N=10,众所周知,没有解决方案.对于许多其他的N(如N=12,N=15等),人们已经搜查,但没有人知道是否有普遍的解决方案.

更长的答案:你所描述的对应于有限的仿射平面.这是一组有限的"点",连同有限的"线"集合(为简单起见,我们可以将其视为点集的子集),满足以下公理:

1. 对于任何两个点,都有一个包含这两点的唯一线.
2. 给定任何线L和任何不在L上的点P,有一条独特的线M,它与L平行并经过(即包含)P.(如果它们没有共同的点,那么M和L被认为是平行的 - 即它们不相交.)
3. 有一个4点的配置,没有三个是共线的.

为了使其符合您的示例:在3x3情况下,您的"点"是数字1到9.您的"行"是"列",配置中的每一行都给出了相互平行的行的集合.

上面的公理1大致对应于您的"完全分布式"属性; axiom 2允许您将"列"组织成行,以便每行包含每个数字一次.Axiom 3并不是那么有趣:它是一个非简并条件,旨在排除前两个公理所允许的简并配置,但与非简并情况没有多少共同之处.

如果你开始搜索,你会发现有限投影平面的很多结果,但有限仿射平面的结果会更少.这是因为任何仿射平面都可以通过在无穷远处添加一条点线来轻松完成到投影平面.相反,给定一个有限的投影平面,您可以移除一条线及其上的所有点以获得仿射平面.因此,如果您可以创建有限的投影平面,则可以创建有限的仿射平面,反之亦然.

以下是从您所拥有的仿射平面开始的完成过程的示例N=3.你有过:

[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]

我们添加了四个新点("无穷远点"),我们将其称为"A","B","C"和"D".每个当前行都会添加一个新点(无穷远处的其中一个点),并且我们还会得到一个新行,其中包含无限远处的这些新点.请注意,之前平行的任何两条线(即,在上面的同一行中)已经在无限远处完成了相同的点,所以现在我们对经常听到的短语"两条平行线在无穷远处相遇"具有非常具体的含义".新结构如下所示:

[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]

所以现在我们有13个点和13个线,这样对于每对不同的点,通过这两个点有一条独特的线,对于每对不同的线,这些线恰好在一个点上相交.而这种精美对称的情况几乎就是有限射影平面(以另一种非简并条件为模).在这种情况下,我们刚刚描述了(有限的同构)有限投影有序投影平面3.

以下是关于有限投影有序平面的一些已知事实n(这里与n此完全对应N):

• 如果n是素数或素数,则有一个有限的投射平面n; 这可以直接和简单地创建从有限域的顺序n,其中,这是你的算法已经做的情况下n是素数
• 还有一些有限的投射平面不是这样产生的:所谓的非Desarguesian平面.有三阶已知的非Desarguesian飞机9,例如
• 没有有限的投射平面6或10(后者通过计算机搜索证明,在20世纪80年代后期花费了大约2000小时的超级计算机时间)
• 目前尚不清楚是否有一个有限的投射平面12(尽管猜测没有)
• 没有已知的有限投影平面,其顺序不是素数或素数
• 一些命令(包括n=14)可以直接由布鲁克 - 莱瑟 - 乔拉定理排除

这里有一些代码构造解决方案,N=4直接作为有限域上的仿射平面,有四个元素,我将称之为GF4.首先,我们需要实现该领域.下面的一个可能是不必要的非显而易见的,并且是为了简化乘法运算而选择的.

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)

现在我们在场上构造标量,然后使用它们首先创建平面中所有点的集合(只是成对的标量),然后是平面中所有线的集合(通过枚举点对):

# 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}

我们的观点目前是成对的对象类型GF4; 显示对应您的问题,我们要重新标记那些与整数更换点1通过16:

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

我们现在可以逐行打印这些行,但是要获取行,我们还需要将行分组为相互并行的组:

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

现在我们可以打印结果,排序友好:

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

这是输出; 它与您计算的输出基本相同.

[(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)]