以最少的交换次数重新排序序列以满足偏序约束
Reorder a sequence with minimum number of swaps to fulfil partial order constraints
输入：元素数组和这些元素子集的偏序，被视为约束集。
输出：满足部分顺序的数组（或任何有序序列）。
问题：如何才能有效地实现重新排序？与原始输入序列相比，引入的反转（或交换）的数量应尽可能少。请注意，可以为任意数量的元素定义偏序（某些元素可能不是其中的一部分）。
上下文： 源于2层图交叉归约的一种情况：交叉归约阶段后，我想重新排序一些节点（因此，部分订单可能只包含一小部分）。
总的来说，我的想法是稍微削弱它并只解决属于偏序的元素的问题（尽管我认为这可能会导致非最佳结果）。因此，如果我有一个序列 A B C D E 并且偏序只包含 A、B 和 E，那么 C 和 D 将留在同一个位置。它让我想起了 Kemeny 分数，但我还不能将其转化为算法。
确定一下：我不是在搜索拓扑排序。这可能会引入比所需更多的反转。
编辑 1：
- 更改了措辞（序列到数组）。
- 用于解决问题的额外 space 的数量可以是任意的（嗯，多项式有界的）大。当然，越少越好 :) 所以，最多像 O(ArrayLen*ArrayLen) 这样的东西就太棒了。
- 为什么交换或反转的最小数量：由于此过程是交叉减少的一部分，输入数组的排序（希望）接近最佳值，就边缘与第二个节点层的交叉而言。然后，每一次额外的交换或反转都可能会再次引入边交叉。 但是在计算输出的过程中，完成的交换或移动的数量并不重要（尽管线性或二次的东西会很酷），因为只有输出质量很重要。现在，我要求约束是完全有序的，并且只检查该顺序的节点，因此解决起来变得微不足道。但是偏序约束会更灵活。
我找到了一篇看起来很有希望的论文："A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction" 迈克尔·福斯特 (Michael Foster)。
连同我的问题下面的评论，它得到了回答。再次感谢@j_random_hacker!
输入：元素数组和这些元素子集的偏序，被视为约束集。
输出：满足部分顺序的数组（或任何有序序列）。
问题：如何才能有效地实现重新排序？与原始输入序列相比，引入的反转（或交换）的数量应尽可能少。请注意，可以为任意数量的元素定义偏序（某些元素可能不是其中的一部分）。
上下文： 源于2层图交叉归约的一种情况：交叉归约阶段后，我想重新排序一些节点（因此，部分订单可能只包含一小部分）。
总的来说，我的想法是稍微削弱它并只解决属于偏序的元素的问题（尽管我认为这可能会导致非最佳结果）。因此，如果我有一个序列 A B C D E 并且偏序只包含 A、B 和 E，那么 C 和 D 将留在同一个位置。它让我想起了 Kemeny 分数，但我还不能将其转化为算法。
确定一下：我不是在搜索拓扑排序。这可能会引入比所需更多的反转。
编辑 1：
- 更改了措辞（序列到数组）。
- 用于解决问题的额外 space 的数量可以是任意的（嗯，多项式有界的）大。当然，越少越好 :) 所以，最多像 O(ArrayLen*ArrayLen) 这样的东西就太棒了。
- 为什么交换或反转的最小数量：由于此过程是交叉减少的一部分，输入数组的排序（希望）接近最佳值，就边缘与第二个节点层的交叉而言。然后，每一次额外的交换或反转都可能会再次引入边交叉。 但是在计算输出的过程中，完成的交换或移动的数量并不重要（尽管线性或二次的东西会很酷），因为只有输出质量很重要。现在，我要求约束是完全有序的，并且只检查该顺序的节点，因此解决起来变得微不足道。但是偏序约束会更灵活。
我找到了一篇看起来很有希望的论文："A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction" 迈克尔·福斯特 (Michael Foster)。 连同我的问题下面的评论，它得到了回答。再次感谢@j_random_hacker!