通过两个比较函数同时对一个列表进行排序、最小化不一致对的算法？
Algorithm to sort one list simultaneously by two comparison functions, minimizing discordant pairs?
假设我有一个元组列表：
[(a1, b1), (a2, b2), ..., (an, bn)]
我可以按 a 或 b 对它们进行排序，但不能同时按两者进行排序。
但是，如果我想尽可能地同时对它们进行排序怎么办？衡量它们排序好坏的一个好方法是按错误顺序的 "a" 值对的数量，加上按错误顺序的 "b" 值对的数量。什么算法可以快速做到这一点？
最小化不同损失函数的算法也很有趣，但我认为最适合我的应用程序的是最小化不一致对。
更新：事实证明在 O(n log n) 时间内有一个非常简单的解决方案。
只需按 a 个组件对列表进行排序，使用 b 个组件作为决胜局。 （反之亦然。）或者，如果它们是数字，您可以按两个分量的总和 a + b 排序。这可以使用任何有效的基于比较的排序算法在 O(n log n) 时间内完成。
这个解决方案之所以有效，是因为损失函数可以写成每对元素的单个损失函数的总和。对于像 (2, 4) vs. (3, 3) 这样的对，无论它们的相对顺序如何都是不一致的，该对的个体损失总是 1。类似地，当两对相等时，例如 (4, 5) 对. (4, 5)，无论它们的相对顺序如何，该对的个体损失都是 0。
唯一的非常量个体损失函数是针对其中一个分量较大而另一个分量较大或等于的对，例如(2, 4) 与 (3, 4)，或 (2, 4) 与 (3, 5)。上面描述的每个排序顺序都会将所有这些对放在它们相对于彼此的最佳顺序中。这同时最小化了损失函数中的每一项，因此它最小化了总损失。
请注意，这 仅适用于二元组列表 。对于 3 元组或更高元组，像这样简单的解决方案是行不通的，但可以调整我原来答案中的想法（见下文）。然而，调整它们并不容易，因为图形不一定是非循环的。
原始答案（扩展）
这可以建模为一种图形问题。每对 (a_i, b_i) 是图中的一个节点。
只要 a_i <= a_j 和 b_i <= b_j 都插入有向边 i → j，除非两者相等。对于 a_i < a_j 和 b_i > b_j 的任何对，反之亦然，以及 a_i = a_j 和 b_i = b_j 的任何对，都没有边。一条边的存在相当于节点i和节点j的相对排序之间的偏好；如果没有边，那么无论这两个节点的相对顺序如何，损失都是相同的。
对于 2 元组的情况，从其构建方式可以很直接地看出该图是非循环的。因此 topological sorting algorithm 会找到一个排序，使得所有边都指向 "forwards"，即节点 i 出现在节点 j 之前，只要有边 i → j。这种排序显然最小化了损失函数，因为它同时最小化了每对 i、j.
的个体损失
结果顺序中唯一不一致的对是那些必然不一致的；那些，无论那对最终以哪种方式结束，a 组件出现故障，或者 b 组件出现故障。
实际实现拓扑排序算法不需要显式构造图；您可以将 "nodes" 和 "edges" 视为 implicit graph, using comparisons to find the edges, instead of looking them up in some kind of graph data structure. To avoid scanning the whole list to find a node's neighbours on every iteration, you can take advantage of the fact that the edge relation is transitive：如果节点 A 仅具有到节点 B、C 和 D 的边，则节点 B 只能具有到 C 和 D 的边。在最坏的情况下，这将花费 O(n²) 时间，但应该比蛮力更有效。
假设我有一个元组列表：
[(a1, b1), (a2, b2), ..., (an, bn)]
我可以按 a 或 b 对它们进行排序，但不能同时按两者进行排序。
但是，如果我想尽可能地同时对它们进行排序怎么办？衡量它们排序好坏的一个好方法是按错误顺序的 "a" 值对的数量，加上按错误顺序的 "b" 值对的数量。什么算法可以快速做到这一点？
最小化不同损失函数的算法也很有趣，但我认为最适合我的应用程序的是最小化不一致对。
更新：事实证明在 O(n log n) 时间内有一个非常简单的解决方案。
只需按 a 个组件对列表进行排序，使用 b 个组件作为决胜局。 （反之亦然。）或者，如果它们是数字，您可以按两个分量的总和 a + b 排序。这可以使用任何有效的基于比较的排序算法在 O(n log n) 时间内完成。
这个解决方案之所以有效，是因为损失函数可以写成每对元素的单个损失函数的总和。对于像 (2, 4) vs. (3, 3) 这样的对，无论它们的相对顺序如何都是不一致的，该对的个体损失总是 1。类似地，当两对相等时，例如 (4, 5) 对. (4, 5)，无论它们的相对顺序如何，该对的个体损失都是 0。
唯一的非常量个体损失函数是针对其中一个分量较大而另一个分量较大或等于的对，例如(2, 4) 与 (3, 4)，或 (2, 4) 与 (3, 5)。上面描述的每个排序顺序都会将所有这些对放在它们相对于彼此的最佳顺序中。这同时最小化了损失函数中的每一项，因此它最小化了总损失。
请注意，这 仅适用于二元组列表 。对于 3 元组或更高元组，像这样简单的解决方案是行不通的，但可以调整我原来答案中的想法（见下文）。然而，调整它们并不容易，因为图形不一定是非循环的。
原始答案（扩展）
这可以建模为一种图形问题。每对 (a_i, b_i) 是图中的一个节点。
只要 a_i <= a_j 和 b_i <= b_j 都插入有向边 i → j，除非两者相等。对于 a_i < a_j 和 b_i > b_j 的任何对，反之亦然，以及 a_i = a_j 和 b_i = b_j 的任何对，都没有边。一条边的存在相当于节点i和节点j的相对排序之间的偏好；如果没有边，那么无论这两个节点的相对顺序如何，损失都是相同的。
对于 2 元组的情况，从其构建方式可以很直接地看出该图是非循环的。因此 topological sorting algorithm 会找到一个排序，使得所有边都指向 "forwards"，即节点 i 出现在节点 j 之前，只要有边 i → j。这种排序显然最小化了损失函数，因为它同时最小化了每对 i、j.
结果顺序中唯一不一致的对是那些必然不一致的；那些，无论那对最终以哪种方式结束，a 组件出现故障，或者 b 组件出现故障。
实际实现拓扑排序算法不需要显式构造图；您可以将 "nodes" 和 "edges" 视为 implicit graph, using comparisons to find the edges, instead of looking them up in some kind of graph data structure. To avoid scanning the whole list to find a node's neighbours on every iteration, you can take advantage of the fact that the edge relation is transitive：如果节点 A 仅具有到节点 B、C 和 D 的边，则节点 B 只能具有到 C 和 D 的边。在最坏的情况下，这将花费 O(n²) 时间，但应该比蛮力更有效。