通过最少的交换次数重新排列序列以满足部分顺序约束。

Question

输入：一个元素数组和一个部分顺序，视为一个约束集合。 输出：满足部分顺序的数组（或任何有序序列）。 问题：如何高效地实现重新排序？与原始输入序列相比，引入的逆序对（或交换次数）应尽可能少。请注意，部分顺序可以针对任意数量的元素进行定义（某些元素可能不是其中的一部分）。 背景：它源于二层图交叉减少中的情况：在交叉减少阶段后，我想重新排列一些节点（因此，部分顺序可能仅包含一小部分）。

通常，我想稍微放松一下这个问题，并仅解决作为部分顺序的元素的问题（尽管我认为这可能会导致非最优结果）。因此，如果我有一个序列A B C D E，而部分顺序仅包含A、B和E，则C和D将保持不变。这让我想起了Kemeny分数，但我还没有把它转化为算法。

只是为了确保：我不是在寻找拓扑排序。这可能会引入比所需更多的逆序对。 编辑1：

• 更改措辞（序列到数组）。
• 用于解决问题的额外空间量可以是任意的（好吧，多项式有界）大。当然，越少越好 :) 因此，最多为O(ArrayLen*ArrayLen)这样的东西将是很棒的。
• 为什么要最小化交换或逆序对数量：因为这个过程是交叉减少的一部分，输入数组的排序（希望）接近于最优，从第二个节点层与边的交叉角度来看。然后，每个额外的交换或逆序对可能会再次引入边的交叉。但在计算输出的过程中，实际上所做的交换或移动次数并不重要（尽管线性或二次的东西会很酷），因为只有输出质量很重要。现在，我要求约束条件处于总顺序中，并且仅检查该顺序的节点，因此变得很容易解决。但是，部分顺序约束将更加灵活。

- HansG

---

所以你有一个数组而不是列表？例如，如果你有ABCDE和部分顺序CEA，那么使用列表最有效的方法就是将A移到末尾。 - maraca

好问题。不过有点欠缺明确的规定。首先，“序列”这个术语比较模糊（正如您可以从之前的评论中看到的那样）。它是数组、列表还是其他数据结构？其次，您是否允许使用额外的内存（例如进行侧面“排序”，决定要进行哪些交换，然后在初始序列上执行它们）？第三，为什么要交换（虽然如果熟悉“上下文”，这可能是显而易见的，但我不熟悉）？为什么要最小化它们的数量，它们很昂贵吗？ - cobarzan

哇，我应该在睡觉前等待答案 :) @maraca：在这种特殊情况下，也许这将是一个好的解决方案。但是你使用了什么样的高效算法来解决它？ - HansG

@cobarzan：答案在我的编辑中，谢谢。 - HansG

不客气 :) 顺便说一下，如果你想让某个人收到你的评论通知，请像这样包含他们的用户名：@j_random_hacker。（请注意，每条评论只能针对一个人。） - j_random_hacker

Answer 1

我找到了一篇看起来很有前途的论文："A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction"，作者是Michael Foster。 结合我的问题下面的评论，问题已经得到解答。再次感谢@j_random_hacker！

- HansG