algorithm - 是否存在尊重最终位置限制并在 O(n log n) 时间内运行的排序算法？

Question

我正在寻找一种排序算法，它尊重每个元素的最小和最大范围1。问题域是一个推荐引擎，它结合了一组业务规则(限制)和推荐分数(值)。如果我们有想要推广的推荐(例如特殊产品或优惠)或我们希望出现在列表顶部附近的公告(例如“这非常重要，请记住验证您的电子邮件地址以参与即将到来的促销事件!”)或靠近列表底部(例如“如果您喜欢这些推荐，请单击此处了解更多...”)，它们将在适当的位置限制下进行策划。例如，这应该始终是最高位置，这些应该在前 10 名或中间 5 名等中。此策划步骤提前完成并在给定时间段内保持固定，并且出于业务原因必须保持非常灵活。

请不要质疑商业目的、UI 或输入验证。我只是想在给定的约束中实现算法。请将此视为学术问题。我将努力提供严格的问题陈述，非常欢迎对问题的所有其他方面提供反馈。

所以如果我们正在排序 char s，我们的数据将具有以下结构

struct {
  char value;
  Integer minPosition;
  Integer maxPosition;
}

哪里 minPosition和 maxPosition可能为空(不受限制)。如果在所有位置限制都为空的算法上调用此方法，或所有 minPosition s 为 0 或更少，并且所有 maxPositions等于或大于列表的大小，那么输出就是 char s 升序。

如果 minPosition，该算法只会对两个元素重新排序和 maxPosition它们的新位置不会违反这两个元素。基于插入的算法将项目提升到列表的顶部并重新排序其余的项目有明显的问题，因为每次迭代后每个后面的元素都必须重新验证；在我看来，这排除了具有 O(n3) 复杂性的此类算法，但我不会在不考虑相反证据的情况下排除此类算法(如果提出)。

在输出列表中，某些元素在它们的值方面将是乱序的，当且仅当位置约束集规定它时。这些输出仍然是 有效 .

A 有效 list 是所有元素都处于不与其约束冲突的位置的任何列表。

安 最佳 list 是一个列表，它不能在不违反一个或多个位置约束的情况下重新排序以更紧密地匹配自然顺序。无效的列表永远不是最优的。我没有一个严格的定义，我可以拼出一个或另一个排序之间的“更紧密匹配”。但是，我认为让直觉引导您或选择类似于 distance metric 的东西相当容易。 .
如果多个输入具有相同的值，则可能存在多个最优排序。您可以论证上述段落因此是不正确的，因为任何一个都可以在不违反约束的情况下重新排序为另一个，因此两者都不是最佳的。但是，任何严格的距离函数都会将这些列表视为相同的，与自然顺序的距离相同，因此允许重新排序相同的元素(因为它是空操作)。
我会称这样的输出为尊重位置约束的正确排序顺序，但一些评论员指出我们并没有真正返回排序列表，所以让我们坚持使用“最佳”。

例如，以下是一个输入列表(以 <char>(<minPosition>:<maxPosition>) 的形式，其中 Z(1:1) 表示 Z 必须在列表的前面， M(-:-) 表示 M 可以在任何最终列表中的位置和自然顺序(仅按值排序)是 A...M...Z )及其最佳顺序。

Input order
A(1:1) D(-:-) C(-:-) E(-:-) B(-:-)
Optimal order
A      B      C      D      E

这是一个简单的例子，表明自然顺序在没有约束的列表中占优势。

Input order
E(1:1) D(2:2) C(3:3) B(4:4) A(5:5)
Optimal order
E      D      C      B      A

这个例子是为了显示一个完全约束的列表是按照给定的顺序输出的。输入已经是 有效 和 最佳 list 。对于此类输入，该算法仍应在 O(n log n) 时间内运行。 (我们的初始解决方案能够将任何完全约束的列表短路以在线性时间内运行；我添加了这个示例，既是为了插入最佳和有效的定义，并且因为我认为一些基于交换的算法将其作为最坏的情况处理。 )

Input order
E(1:1) C(-:-) B(1:5) A(4:4) D(2:3)
Optimal Order
E      B      D      A      C

E被限制为 1:1 ，因此它在列表中排在第一位，即使它的值最低。 A同样受限于 4:4 ，所以也是乱序的。 B与 C 具有基本相同的约束并且可能出现在最终列表中的任何位置，但 B将在 C 之前因为值(value)。 D可能在位置 2 或 3，所以它出现在 B 之后由于自然排序但在 C 之前因为它的限制。

请注意，尽管与自然顺序(仍然是 A 、 B 、 C 、 D 、 E )有很大不同，但最终顺序是正确的。如上一段所述，此列表中的任何内容都不能在不违反一个或多个项目的约束的情况下重新排序。

Input order
B(-:-) C(2:2) A(-:-) A(-:-)
Optimal order
A(-:-) C(2:2) A(-:-) B(-:-)

C保持不动，因为它已经处于唯一有效的位置。 B被重新排序到最后，因为它的值小于两者 A的。实际上，会有额外的字段来区分这两个 A 's，但从算法的角度来看，它们是相同的，保留或反转它们的输入顺序是最佳解决方案。

Input order
A(1:1) B(1:1) C(3:4) D(3:4) E(3:4)
Undefined output

此输入无效有两个原因:1) A和 B都被限制在位置 1 和 2) C , D , 和 E被限制在一个只能容纳 2 个元素的范围内。换句话说，范围 1:1和 3:4被过度约束。但是，约束的一致性和合法性由 UI 验证强制执行，因此如果它们不正确，则正式不是算法问题，并且在这种情况下，算法可以返回尽力而为的排序或原始排序。可以考虑将这样的输入传递给算法 undefined behavior ;任何事情都可能发生。所以，对于剩下的问题......

所有输入列表都将具有最初处于有效位置的元素。

排序算法本身可以假设约束有效并且存在最优顺序。 2

我们目前已经确定了自定义选择排序(运行时复杂度为 O(n2))，并合理证明它适用于所有位置限制有效且一致的输入(例如，对于给定的位置或位置范围没有超额预订)。

是否有一种排序算法可以保证返回最优的最终顺序并以优于 O(n2) 的时间复杂度运行？3

我觉得可以通过提供一个接受每个元素的候选目标位置的自定义比较器来修改库标准排序算法来处理这些约束。这将等同于每个元素的当前位置，因此可能修改值保持类以包含元素的当前位置并在比较 ( .equals() ) 和交换方法中进行额外计算就足够了。

然而，我想得越多，在 O(n log n) 时间内运行的算法在这些限制下无法正常工作。直观地说，此类算法基于运行 n 次比较 log n 次。 log n 是通过利用分治机制实现的，该机制仅比较某些职位的某些候选人。

换句话说，对于任何 O(n log n) 排序算法，都存在具有有效位置约束(即反例)的输入列表，其中将候选元素与元素(或快速排序和变体的情况下的范围)进行比较。它无法交换，因此永远不会移动到正确的最终位置。如果这太模糊了，我可以想出一个合并排序和快速排序的反例。

相比之下，O(n2) 排序算法进行详尽的比较，并且始终可以将元素移动到其正确的最终位置。

提出实际问题:当我推断 O(n log n) 排序不能保证找到有效顺序时，我的直觉是否正确？如果是这样，你能提供更具体的证据吗？如果没有，为什么不呢？对此类问题是否有其他现有研究？

1:我无法找到一组搜索词，这些搜索词将我指向此类排序算法或约束的任何具体分类方向；这就是为什么我要问一些关于复杂性的基本问题。如果有此类问题的术语，请发布。

2:验证是一个单独的问题，值得自己研究和算法。我很确定可以在线性时间内证明有效订单的存在:

分配长度等于您的列表的元组数组。每个元组是一个整数计数器 k 和一个用于相对分配权重的 double 值 v。

遍历列表，将每个元素位置约束的小数值添加到相应的范围，并将其计数器加 1(例如，10 的列表上的范围 2:5 将 0.4 添加到我们元组上的 2、3、4 和 5 中的每一个列表，也增加每个的计数器)

遍历元组列表和

如果没有条目的值 v 大于从 1 到 k 的 1/k 系列的总和，则存在有效订单。

如果有这样一个元组，它所处的位置就被过度约束了；抛出异常、记录错误、使用 double 数组更正问题元素等。

编辑:这个验证算法本身实际上是 O(n2)。最坏的情况，每个元素都有约束 1:n ，你最终会遍历你的 n 个元组列表 n 次。这仍然与问题的范围无关，因为在真正的问题域中，约束被强制执行一次并且不会改变。

确定给定列表的顺序是否有效甚至更容易。只需根据其约束检查每个元素的当前位置。

3:无可否认，这有点过早优化。我们最初的用途是用于相当小的列表，但我们着眼于扩展到更长的列表，所以如果我们现在可以优化，我们现在会获得很小的性能提升，稍后会获得很大的性能提升。此外，我的好奇心被激起了，如果有关于这个主题的研究，我希望看到它并(希望)从中学习。

Answer 1

关于解决方案的存在:您可以将其视为二部有向图，其中一组顶点 (U) 是 k 值，另一组 (V) 是 k 等级(1 到 k)，以及每个顶点的弧在 U 到其在 V 中的有效等级。那么解的存在就相当于最大匹配是一个双射。检查这一点的一种方法是向 U 中的每个顶点添加一个带有弧的源顶点，以及一个带有来自 V 中每个顶点的弧的汇顶点。将每条边的容量分配为 1，然后找到最大流量。如果它是 k 那么有一个解决方案，否则没有。

http://en.wikipedia.org/wiki/Maximum_flow_problem

--edit-- O(k^3) 解决方案:首先排序以找到每个顶点的排序等级(1-k)。接下来，将您的值和等级视为 2 组 k 个顶点，U 和 V，从 U 中的每个顶点到 V 中所有合法等级的加权边。分配每条边的权重是与排序中的顶点的距离订单。例如，如果 U 是 10 到 20，那么 10 的自然等级是 1。从值 10 到等级 1 的边的权重为零，到等级 3 的权重为 2。接下来，假设所有缺失的边都存在并赋予它们无限的权重。最后，在 O(k^3) 中找到“MINIMUM WEIGHT PERFECT MATCHING”。

http://www-math.mit.edu/~goemans/18433S09/matching-notes.pdf

这并没有利用 U 中每个元素的合法等级是连续的这一事实，这可能有助于将运行时间降低到 O(k^2)。