如何构建一个N*(N+1)的矩阵，其数量在1~N*N之间且完全分布？
How to build a N*(N+1) matrix with number in range of 1~N*N and totally distributed?
假设给定一个数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)
简短回答：这是组合学领域的一个已知和研究过的问题，并且（不想让您气馁）似乎很难通过计算解决。对于 N 素数或素数幂，一旦您知道如何生成示例就很容易。对于N=6或N=10，known无解。还有很多N（如N=12、N=15等），大家搜索过，不知道有没有大体的解决办法
更长的回答：你所描述的对应一个finite affine plane。这是 "points" 的有限集合，以及 "lines" 的有限集合（为简单起见，我们可以将其视为点集的子集），满足以下公理：
- 对于任意两个点，都有一条包含这两个点的唯一直线。
- 给定任何一条线 L 和任何不在 L 上的点 P，有一条唯一的线 M 平行于 L 并穿过（即包含）P。（这里 M 和 L 被认为是平行的，如果它们在常见 - 即它们不相交。)
- 有 4 个点的配置，没有三个点共线。
为了使这与您的示例相对应：在 3x3 的情况下，您的 "points" 是数字 1 到 9。您的 "lines" 是 "columns"，并且您的每一行配置给出了一组相互平行的线。
上面的公理1大致对应你的"totally distributed"属性；公理 2 可以让您将 "columns" 组织成行，以便每行只包含每个数字一次。公理 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]
我们添加了四个新点 ("points at infinity")，我们称之为 "A"、"B"、"C" 和 "D"。每条当前线都会添加一个新点（其中一个位于无穷远处），我们还会得到一条新线，正好由这些位于无穷远处的新点组成。请注意，以前平行的任何两条线（即在上面的同一行中）都已完成 相同 点在无穷远，所以现在我们对经常有一个非常具体的含义- 听到短语 "two parallel lines meet at infinity"。新结构如下所示：
[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 的 finite field 创建，这是您的算法在 n 是质数 的情况下已经做的事情
- 也有有限射影平面不是这样产生的：所谓的非笛沙格平面。有三个已知的非笛沙格平面
9，例如
- 不存在阶数有限的投影平面
6或10（后者已在 1980 年代后期用超级计算机耗时约 2000 小时的计算机搜索得到证明）
- 未知是否存在有限阶射影平面
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)]
假设给定一个数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)
简短回答：这是组合学领域的一个已知和研究过的问题，并且（不想让您气馁）似乎很难通过计算解决。对于 N 素数或素数幂，一旦您知道如何生成示例就很容易。对于N=6或N=10，known无解。还有很多N（如N=12、N=15等），大家搜索过，不知道有没有大体的解决办法
更长的回答：你所描述的对应一个finite affine plane。这是 "points" 的有限集合，以及 "lines" 的有限集合（为简单起见，我们可以将其视为点集的子集），满足以下公理：
- 对于任意两个点，都有一条包含这两个点的唯一直线。
- 给定任何一条线 L 和任何不在 L 上的点 P，有一条唯一的线 M 平行于 L 并穿过（即包含）P。（这里 M 和 L 被认为是平行的，如果它们在常见 - 即它们不相交。)
- 有 4 个点的配置，没有三个点共线。
为了使这与您的示例相对应：在 3x3 的情况下，您的 "points" 是数字 1 到 9。您的 "lines" 是 "columns"，并且您的每一行配置给出了一组相互平行的线。
上面的公理1大致对应你的"totally distributed"属性；公理 2 可以让您将 "columns" 组织成行，以便每行只包含每个数字一次。公理 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]
我们添加了四个新点 ("points at infinity")，我们称之为 "A"、"B"、"C" 和 "D"。每条当前线都会添加一个新点（其中一个位于无穷远处），我们还会得到一条新线，正好由这些位于无穷远处的新点组成。请注意，以前平行的任何两条线（即在上面的同一行中）都已完成 相同 点在无穷远，所以现在我们对经常有一个非常具体的含义- 听到短语 "two parallel lines meet at infinity"。新结构如下所示：
[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的 finite field 创建，这是您的算法在n是质数 的情况下已经做的事情
- 也有有限射影平面不是这样产生的：所谓的非笛沙格平面。有三个已知的非笛沙格平面
9，例如 - 不存在阶数有限的投影平面
6或10（后者已在 1980 年代后期用超级计算机耗时约 2000 小时的计算机搜索得到证明） - 未知是否存在有限阶射影平面
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)]