有效地构造每行中具有唯一数字的方阵

Question

nxn需要使用所需属性构建大小矩阵.

1. n甚至.(作为算法的输入)
2. 矩阵应包含整数0到n-1
3. 主对角线应仅包含零,矩阵应对称.
4. 每行中的所有数字都应该不同.

对于各种n,可能需要任何一种可能的输出.

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

现在,我想到的唯一想法是以递归方式强制构建组合并修剪.

如何以迭代的方式有效地完成这项工作？

Answer 1

我们知道每一行必须包含每个数字。同样，每一行包含每个数字。

让我们采用从 0 开始索引的 CS 约定。

首先，考虑如何将 1 放入矩阵中。从 1 到 n-1 中选择一个随机数 k0。将 1 放置在第 0 行的位置 (0,k0) 处。在第 1 行中，如果 k0 = 1，在这种情况下已经放置了一个 1。否则，有 n-2 个空闲位置，并将 1 放置在位置 (1,k1) 处。以此类推，直到所有1都放置完毕。最后一排恰好有一个空闲位置。

接下来，重复 2 个必须适合其余位置的操作。

现在的问题是我们可能无法真正完成这个正方形。我们可能会发现有一些限制导致无法填写最后一位数字。问题在于，检查部分填充的拉丁方是 NP 完全的。（维基百科）这基本上意味着计算密集型并且没有已知的捷径算法。所以我认为你能做的最好的事情就是生成方块并测试它们是否有效。

如果您只想要每个 n 一个特定的正方形，那么可能有更简单的方法来生成它们。特德·霍普在他的评论《拉丁方》中给出了链接。Simple Construction确实提供了一种从整数 mod n 相加开始生成平方的方法。