python - 如何构建一个 N*(N+1) 矩阵，其数量在 1~N*N 范围内且完全分布？

Question

假设对于给定的数字 N，生成一个具有 N+1 行的矩阵，每行有 N 列，每列有 N 个数字，范围为 [1, N^2]。而矩阵有这个特点:每列有N个数字，数字完全分布在其他行中。

Sorry for that English is not my mother language, I tried my best to describe the problem clearly, If you have better description for this problem, please teach me how to.

例如 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]

[1, 5, 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,2,3],[4,5,6],[7,8,9]

对于接下来的行，我从第一行中选择一个具有不同偏移量的数字。

以下是我如何在 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 ，它是 known没有解决方案。对于许多其他 N (例如， N=12 ， N=15 等)，人们已经搜索过，但没有人知道是否有普遍的解决方案。

更长的答案:您所描述的对应于 finite affine plane .这是一组有限的“点”，以及有限的“线”集合(为简单起见，我们可以将其视为点集的子集)，满足以下公理:

对于任何两点，都有一条包含这两个点的唯一线。

给定任何线 L 和不在 L 上的任何点 P，有一条独特的线 M 与 L 平行并穿过(即包含)P。(如果 M 和 L 没有共同点，则它们被认为是平行的——即不相交。)

有 4 个点的配置，因此没有三个点共线。

为了使其与您的示例相对应:在 3x3 的情况下，您的“点”是数字 1 到 9。您的“线”是“列”，并且您的配置中的每一行都给出了一组相互平行的线。

上面的公理 1 大致对应于您的“完全分布式”属性；公理 2 可让您将“列”组织成行，以便每行只包含每个数字一次。公理 3 并不是那么有趣:它是一个非简并条件，旨在排除前两个公理允许的简并配置，但在其他方面与非简并情况没有太多共同之处。

如果您开始搜索，您会发现 finite projective planes 的许多结果。 ，但对于有限仿射平面更少。这是因为通过在无穷远处添加一条线，任何仿射平面都可以轻松完成为投影平面。相反，给定一个有限的射影平面，您可以删除一条线及其上的所有点以获得仿射平面。因此，如果您可以创建有限的射影平面，就可以创建有限的仿射平面，反之亦然。

这是从您拥有的仿射平面开始的完成过程的示例 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 ;这可以直接和简单地从 finite field 创建订购 n ，这是您的算法在 n 的情况下已经执行的操作是素数

还有一些有限的射影平面不会以这种方式出现:所谓的非笛沙格平面。存在三个已知的非笛沙格平面 9 ，例如

没有阶的有限射影平面 6或 10 (后者在 1980 年代后期通过计算机搜索得到了证明，该搜索花费了大约 2000 小时的 super 计算机时间)

未知是否存在有限的阶射影平面12 (虽然推测没有)

没有已知的有限射影平面的阶不是素数或素数幂

一些订单(包括 n=14 )可以直接通过 Bruck-Ryser-Chowla theorem 排除

下面是为 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)]