输入：元素数组和这些元素子集的偏序，被视为约束集。
输出：满足偏序的数组（或任何有序序列）。
问题：如何有效地实现重新排序？与原始输入序列相比，引入的反转（或交换）的数量应尽可能小。请注意，可以为任意数量的元素定义偏序（某些元素可能不是其中的一部分）。
上下文：它源于 2 层图交叉减少的情况：在交叉减少阶段之后，我想重新排序一些节点（因此，部分顺序可能只包含一个小子集）。
总的来说，我的想法是稍微弱化这一点，并仅针对属于偏序的元素解决问题（尽管我认为这可能会导致非最佳结果）。因此，如果我有一个序列 ABCDE 并且偏序只包含 A、B 和 E，那么 C 和 D 将保持在同一个位置。它以某种方式让我想起了 Kemeny 分数，但我还不能把它变成算法。
可以肯定的是：我不是在寻找拓扑排序。这可能会引入比所需更多的反转。
编辑1：
- 更改了措辞（序列到数组）。
- 用于解决问题的额外空间量可以是任意的（嗯，多项式有界）。当然，越少越好 :) 所以，像 O(ArrayLen*ArrayLen) 这样的东西最多会很棒。
- 为什么交换或反转的最小数量：由于此过程是交叉减少的一部分，因此输入数组的排序（希望）接近最佳值，就与第二节点层的边缘交叉而言。然后，每一次额外的交换或反转可能会再次引入边缘交叉。但是在计算输出的过程中，完成的交换或移动的数量并不重要（尽管再次，线性或二次的东西会很酷），因为只有输出质量很重要。现在，我要求约束是一个总顺序，并且只检查该顺序的节点，因此解决它变得微不足道。但是偏序约束会更加灵活。