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