algorithm - 非困惑定理的证明

Question

<分区>

Answer 1

简单段落解释:如果对行进行排序，并且你有A列，B列，一个数字r在 A 列中，和 n A 列中的数字小于或等于 r , 那么: 最多有 n B 列中小于 r 的数字(对应于 A 列中的 n 数字)。其余的等于或大于 r .你可以拿r为 A 列中的任意数字，结果仍然成立。然后对每一列使用相同的逻辑。

带图片的详细解释:

我们可以从一个已经按行排序的简单矩阵开始:

如果我们按第一个数字对彩色 block 进行排序，我们会得到这个矩阵(请注意，这实际上是对 A 列进行排序，但同时也将 B 列拖到其中):

现在，在下一张图片中，2 小于或等于蓝色的所有内容。因此，无论您如何对 B 列进行排序，第 1 行仍将被排序:

在下图中，因为行和列 A 已排序，所以 3 小于或等于紫色的所有内容。因此，对B列进行排序时，3旁边的数一定大于等于它。因此，我们知道第 2 行将保持排序。

在下一张图片中，因为行和列 A 已排序，所以 3 小于或等于黑色的所有内容。因此，对B列进行排序时，3旁边的数一定大于等于它。因此，我们知道第 3 行将保持排序。

对于最后一行，我们可以使用相同的逻辑。但是，我们还可以注意到，显然有一个数字可以使最后一行保持排序(当前紧挨着它的数字 7)。如果 7 不存在，则在对 B 列排序后，另一个 > 7 必须 存在。第 4 行将保持排序:

我们最终得到这个:

对于尚未排序的列，行将并不总是排序。例如，请注意这个矩阵，其行已排序:

[4 7 8  9]
[1 5 10 12]
[2 3 6  11]

如果我们对上述矩阵的前两列进行排序，我们会得到:

[1 3 8  9]
[2 5 10 12]
[4 7 6  11]

第 3 行未排序。但是，它将获得编号 10在对第 3 列进行排序后，一切都会好起来的。