我需要设计一种算法来判断给定的整数矩阵是否是有效的拉丁方。我以前从未与拉丁方合作过，所以我不知道从哪里开始。经过一番研究，我只发现了写拉丁方格的算法。我唯一想到的是所有列和行的总和应该是相同的，但是我必须检查每个数字是否在同一行和列中重复。这样做，该程序将花费大量时间。我正在使用 C++。
问问题
617 次
1 回答
0
这样做，该程序将花费大量时间。
不，因为你可以在到达终点之前拒绝很多矩阵。所以算法会很快失败。工作算法的最差估计是O(n*(n+1))（我假设您只评估维度为 n*n 的方阵）。但是平均算法会好得多 - 因为它会在第一次发现不等式时失败。
更新：
平均复杂度可以粗略估计为真实拉丁方的数量与可能的方的数量。为此，我们需要引入理解normalized方。下面的两个正方形在直觉上是相同的：
[ 1 2 [5 7
2 1 ] 7 5]
因此，为了标准化这一点，我们可以使用 n*n 平方的数字 1...n 的替换。所以第一种形式获胜。
对于归一化正方形Wiki 提供了一个估计 
你怕了吗？但是对于平均值，我们还需要将此公式除以矩阵的总数。为此，请参阅此公式http://en.wikipedia.org/wiki/Combination
于 2013-04-26T16:57:40.370 回答