如何判断三维正方形是否是拉丁正方形
如何判断三维正方形是否是拉丁正方形
提问于 2013-04-27 00:49:31
我需要设计一种算法来判断给定的整数矩阵是否为有效的拉丁方。我以前从来没有使用过拉丁Sqares，所以我不知道从哪里开始。经过一些研究，我只找到了写拉丁方的算法。我遇到的唯一一件事是所有列和行的和应该是相同的，但是我必须检查每个数字是否在相同的行和列中重复。这样做，程序将有很大的时间成本。我使用的是C++。
回答 1
Stack Overflow用户
发布于 2013-04-27 00:57:40
这样做，程序将会有很大的时间开销。
不，因为你可以在到达结尾之前拒绝很多矩阵。所以算法很快就会失败。工作算法的最差估计是O(n*(n+1)) (我假设您只评估维数为n*n的方阵)。但平均算法会好得多-因为它会像第一个不平等发现的那样失败。
更新：平均复杂度可以是粗略的，近似估计为真实拉丁方的数量与可能的方块的数量。要做到这一点，我们需要介绍了解normalized square。下面的两个方块直观上是相同的：
[ 1 2 [5 7
2 1 ] 7 5]因此，为了使其规范化，我们可以使用n*n平方的数字1…n的替换。所以第一种形式胜出。
对于归一化的正方形Wiki provides an estimation
你害怕吗？但是对于平均值，我们还需要将这个公式除以矩阵的总数。要做到这一点，请参阅此公式http://en.wikipedia.org/wiki/Combination
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/16241426
复制相关文章
相似问题
腾讯云开发者
