给定成对排序 [英] Sorting given pairwise orderings
问题描述
我有 n 个变量（ Var 1 ... Var n ），但不知道它们的确切值。在这些 n 变量之间的 n选择2 成对排序是已知的。例如，已知 Var 5< = Var 9 ， Var 9< = Var 10 等开启所有对。此外，还已知这些成对的顺序是一致的，并且不会导致整个退化的退化情况。也就是说，在上面的示例中，不存在等式 Var 10 <== Var 5 。
什么
问题不是如何解决所有问题的最有效排序算法？
排序（使用您语言的标准排序），但是如何将排序标准输入排序算法。
在大多数语言中，您需要提供 int比较（T a，T b）其中T是元素的类型，根据谁更大而返回-1、0或1。
因此，在给定一对元素的情况下，您需要快速访问存储（所有）成对排序的数据结构。
所以问题不会那么多 Var 10 <= Var 5 存在（不一致），但更多的是 Var 5 <== Var 10 确保出席 ？如果是这种情况，则可以使用散列成对的元素来测试O（1）中约束的存在，否则，您需要找到a和b之间的传递关系，该关系甚至不存在（从OP，如果我们谈论的是部分或全部订单，即对于所有a，b，我们确保a< b或b< a或a = b（总订单）。
在大约N ^ 2个条目的最坏情况下，此哈希值相当大。构建它仍然需要探索传递链接，这很昂贵。
以下链接可能意味着地图将元素与一组（立即）较小的元素进行比较，将a与b进行比较时，如果（map（a）包含b）或（map（b）包含a），您可以立即回答，否则需要递归map的元素（a）和map（b），复杂度非常差。最终，您仍然会累积一些较小的值来构建测试。
也许 a< = b 的约束数量少，仅应用置换o当f a和b不遵守约束并遍历约束到定点时（所有约束在一个完整的回合中应用而没有影响）可能会更有效。至少是内存中的O（1）。
一种变体可以使用稳定排序（保留不可比条目的顺序）对约束子集进行几次排序
最后，用输入数据计算最大值为O（约束数），因此您可以重复计算最大值，将其添加到末尾。目标，消除使用它的约束，冲洗并重复。我会使用堆栈来存储最大的元素，直到给定的约束索引，这样您就可以回溯到该位置，而不用从头开始。
I have n variables (Var 1 ... Var n) and do not know their exact values. The n choose 2 pairwise ordering between these n variables are known. For instance, it is known that Var 5 <= Var 9, Var 9 <= Var 10 and so on for all pairs. Further, it is also known that these pairwise orderings are consistent and do not lead to a degenerate case of equality throughout. That is, in the above example the inequality Var 10 <= Var 5 will not be present.
What is the most efficient sorting algorithm for such problems which gives a sorting of all variables?
The question is not so much how to sort (use the standard sort of your language) but how to feed the sort criterion to the sorting algorithm.
In most languages you need to provide a int comparison (T a, T b) where T is the type of elements, that returns -1, 0 or 1 depending on who is larger.
So you need a fast access to the data structure storing (all) pairwise orderings, given a pair of elements.
So the question is not so much will Var 10 <= Var 5 be present (inconsistent) but more is Var 5 <= Var 10 ensured to be present ? If this is the case, you can test presence of the constraint in O(1) with a hash set of pairs of elements, otherwise, you need to find a transitive relationship between a and b, which might not even exist (it's unclear from OP if we are talking of a partial or total order, i.e. for all a,b we ensure a < b or b < a or a = b (total order).
With roughly worst case N^2 entries, this hash is pretty big. Building it still requires exploring transitive links which is costly.
Following links probably means a map of elements to sets of (immediately) smaller elements, when comparing a to b, if (map(a) contains b) or (map(b) contains a) you can answer immediately, otherwise you need to recurse on the elements of map(a) and map(b), with pretty bad complexity. Ultimately you'll still be cumulating sets of smaller values to build your test.
Perhaps if you have a low number of constraints a <= b, just applying a permutation of a and b when they do not respect the constraint and iterating over the constraints to fixpoint (all constraints applied in one full round with no effect) could be more efficient. At least it's O(1) in memory.
A variant of that could be sorting using a stable sort (preserves order of incomparable entries) several times with subsets of the constraints.
Last idea, computing a Max with your input data is O(number of constraints), so you could just repeatedly compute the Max, add it at the end of the target, remove constraints that use it, rinse and repeat. I'd use a stack to store the largest element up to a given constraint index, so you can backtrack to that rather than restart from scratch.
这篇关于给定成对排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
