输入:元素数组和这些元素子集的偏序，被视为约束集。
输出:满足部分顺序的数组(或任何有序序列)。
问题:如何才能有效地实现重新排序？与原始输入序列相比，引入的反转(或交换)的数量应尽可能少。请注意，可以为任意数量的元素定义偏序(某些元素可能不是其中的一部分)。
上下文: 源于2层图交叉归约的一种情况:在交叉归约阶段后，我想对一些节点进行重新排序(因此，偏序可能只包含一个小子集)。
总的来说，我的想法是稍微削弱它并只解决属于偏序的元素的问题(尽管我认为这可能会导致非最佳结果)。因此，如果我有一个序列 A B C D E 并且偏序只包含 A、B 和 E，那么 C 和 D 将留在同一个位置。它让我想起了 Kemeny 分数，但我还不能将其转化为算法。
可以肯定的是:我不是在搜索拓扑排序。这可能会引入比所需更多的反转。
编辑 1:
- 更改了措辞(序列到数组)。
- 解决问题的额外空间量可以是任意大的(好吧，多项式有界)。当然，越少越好 :) 所以，最多像 O(ArrayLen*ArrayLen) 这样的东西会很棒。
- 为什么交换或反转的最小数量:由于此过程是交叉减少的一部分，输入数组的排序(希望)接近最佳，就边缘与第二个节点层的交叉而言。然后，每一次额外的交换或反转都可能会再次引入边交叉。 但是在计算输出的过程中，完成的交换或移动的数量并不重要(尽管线性或二次的东西会很酷)，因为只有输出质量才是重要的。现在，我要求约束是完全有序的，并且只检查该顺序的节点，因此解决起来变得微不足道。但是偏序约束会更加灵活。
最佳答案
我找到了一篇看起来很有前途的论文:Michael Foster 撰写的“用于约束两级交叉减少的快速简单启发式”。 连同我的问题下面的评论，它得到了回答。再次感谢@j_random_hacker!
关于algorithm - 以最少的交换次数重新排序序列以满足偏序约束，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36119764/