Jim*_*ite 5 algorithm permutation cycle-detection
给定一个大小矩阵,m X n行或列中没有重复值,是否有一种检测周期的有效方法？
例如,这是一个示例矩阵:
3 5 2 9 7 4
4 3 6 1 8 7
1 4 7 5 2 9
9 8 3 2 6 1
2 6 8 7 3 5
它至少有一个大小为3的排列周期:
3 5 2 9 7 4
4 8 3 1 6 7
1 4 7 5 2 9
9 6 8 2 3 1
2 3 6 7 8 5
第2,4和5行中的值3,6和8形成一个循环.
这个问题与Kakuro谜题有关.与解决它们无关,而是试图检测特定网格的任何布局是否使其不合适.任何类型的循环都会使该特定布局无效 - 因为两个布局的行和列的总和是相同的.
我认为对于 nxn 网格，您可以在 O(n^3) 时间内完成此操作。
主意
考虑您的示例网格，并假设左上角的 3 和 5 是否可以出现在拉丁子正方形中。
(3) (5) 2 9 7 4
4 8 3 1 6 7
1 4 7 5 2 9
9 6 8 2 3 1
2 3 6 7 8 5
因为我们想要一个拉丁方格，所以我们被迫将 3 包含在 (5) 列中（所有值必须出现在每列中），以及附近的 2 （必须形成一个方格）：
(3) (5) 2 9 7 4
4 8 3 1 6 7
1 4 7 5 2 9
9 6 8 2 3 1
(2) (3) 6 7 8 5
我们可以继续做这个蕴涵一段时间，但是我们很快就会遇到一个问题：左行不包含 5。包含左上角的 3 和左上角的 5 会导致矛盾。
一般来说，每当我们在同一行或同一列中包含 2 个值时，该对将强制包含最多 4 个其他值和/或意味着矛盾。我们希望利用这种蕴涵结构来快速消除不好的解决方案，只留下好的解决方案。
制作图表
既然我们有了这个有用的蕴涵结构，我们就应该探索它。为每个水平和垂直值对创建一个节点，并在每当一对值意味着必须包含另一对值时在这些节点之间插入有向边。还有一个“矛盾”节点。例如，示例中{(0, 0), (0, 1)}对应于左上角的对将具有指向、和 的传出边缘。(3) (5){(0, 0), (4, 0)}{(0, 1), (4, 1)}contradiction
结果是一个图表，其中有许多节点指向矛盾，并且可能有一些节点在循环中互相指向。去掉矛盾节点以及任何直接或间接指向它的东西，剩下的应该是循环，并且任何循环都应该对应于一个拉丁方。
正确性
老实说，我不确定这是否正确。很明显，在每个添加的对的意义上，拉丁方并没有立即进行彻底的正确性检查，导致所有必要的工作发生......但我认为所有会被遗漏的坏情况都是值重复的情况，并且这保证不会在输入中发生。
还需要做更多的工作。
复杂
图中有 O(n^3) 个节点，因为行或列中有 O(n^2) 对，并且 O(n) 行+列。还有 O(n^3) 条边，因为每个节点最多有 4 个出边。
假设您使用的是边列表，删除指向的内容所contradiction花费的时间与节点数量成正比。只需沿着上游边缘进行向后洪水填充即可。
检测循环所需的时间与节点和边的数量成正比：根据节点的出节点数量（最多 4 个）对节点进行分桶，并不断删除 0-out 桶中的节点并重新对受影响的节点进行分桶，直到完毕。如果还有什么，那就是一个循环。
由于所有操作所花费的时间与节点和边的数量成正比，并且我们有 O(n^3) 个节点+边，因此整个算法需要 O(n^3) 时间。