nxn需要构建具有所需属性的大小矩阵。
n甚至。（作为算法的输入）- 矩阵应该包含从
0到的整数n-1 - 主对角线应该只包含零，矩阵应该是对称的。
- 每行中的所有数字都应该不同。
对于各种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
现在我想到的唯一想法是暴力构建组合递归和修剪。
如何以迭代的方式有效地完成这项工作？
问问题
788 次
3 回答
3
IMO，您可以通过算法处理您的答案来处理这个问题：
如果8x8结果是：
0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0
您实际上有4x4以下模式中的两个矩阵的矩阵：
m0 => 0 1 2 3 m1 => 4 5 6 7 pattern => m0 m1
1 0 3 2 5 4 7 6 m1 m0
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
而且每4x4一个都是两个2x2矩阵的矩阵，关系到 2 的幂：
m0 => 0 1 m1 => 2 3 pattern => m0 m1
1 0 3 2 m1 m0
在其他解释中，我应该说您有一个2x2矩阵，0然后通过用新矩阵替换每个单元格1来将其扩展为矩阵：4x42x2
0 => 0+2*0 1+2*0 1=> 0+2*1 1+2*1
1+2*0 0+2*0 1+2*1 0+2*1
result => 0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
现在再次展开：
0,1=> as above 2=> 0+2*2 1+2*2 3=> 0+2*3 1+2*3
1+2*2 0+2*2 1+2*3 0+2*3
我可以通过这个 C# 示例代码计算每个单元格的值：
// i: row, j: column, n: matrix dimension
var v = 0;
var m = 2;
do
{
var p = m/2;
v = v*2 + (i%(n/p) < n/m == j%(n/p) < n/m ? 0 : 1);
m *= 2;
} while (m <= n);
于 2016-10-01T08:49:12.137 回答
0
我可能是错的，但如果你只是想打印一个对称表 - 拉丁方格的特殊情况，与映射到环 {0 的 powerset({0,1,..,n}) 上的对称差分运算表同构,1,2,..,2^n-1}。
也可以使用XOR(i,j)wherei和jaren*n表索引来生成这样的表。
例如：
def latin_powerset(n):
for i in range(n):
for j in range(n):
yield (i, j, i^j)
打印来自之前定义的上述对称拉丁方格的特殊情况生成器的元组：
def print_latin_square(sq, n=None):
cells = [c for c in sq]
if n is None:
# find the length of the square side
n = 1; n2 = len(cells)
while n2 != n*n:
n += 1
rows = list()
for i in range(n):
rows.append(" ".join("{0}".format(cells[i*n + j][2]) for j in range(n)))
print("\n".join(rows))
square = latin_powerset(8)
print(print_latin_square(square))
输出：
0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0
也可以看看
这涵盖了拉丁方格的更通用情况，而不是上面简单代码的超对称情况：
于 2020-03-20T21:32:52.890 回答
0
我们知道每一行必须包含每个数字。同样，每一行包含每个数字。
让我们采用从 0 开始的索引的 CS 约定。
首先，考虑如何将 1 放入矩阵中。选择一个随机数 k0，从 1 到 n-1。将第 0 行中的 1 放在位置 (0,k0)。在第 1 行，如果 k0 = 1，在这种情况下已经放置了一个。否则，有 n-2 个空闲位置并将 1 放在位置 (1,k1)。以这种方式继续，直到所有的 1 都放好。在最后一排正好有一个空闲位置。
接下来，重复必须适合其余位置的 2 个。
现在的问题是我们可能无法真正完成正方形。我们可能会发现有一些限制使得无法填写最后一位数字。问题是检查部分填充的拉丁方格是 NP 完全的。（维基百科）这基本上意味着相当密集的计算并且没有知道的捷径算法。所以我认为你能做的最好的就是生成正方形并测试它们是否有效。
如果您只希望每个 n 有一个特定的正方形，那么可能有更简单的方法来生成它们。Ted Hopp 在他的评论中给出的链接Latin Squares。简单构造确实提供了一种生成平方的方法，该方法从整数 mod n 的加法开始。
于 2016-09-12T15:14:09.510 回答