时间戳

首页 > 解决方案 > 检查总订单是否细化了部分订单

python - 检查总订单是否细化了部分订单

问题描述

考虑整数对 (x,y)。我们强加一个偏序，使得 (x,y) ≤ (x',y') wrt。x ≤ x' 和 y ≤ y' 的偏序。如果 (x,y) ≤ (x',y') 和 (x',y') ≤ (x,y)，我们说 (x,y) 和 (x',y') 是不可比的。

现在，我有一个ls这样的配对列表。我想检查该列表的顺序是否细化了上面定义的部分顺序；即，我需要检查列表中任何元素的右侧是否没有更小的元素。

当然我可以做到以下几点：

def leq_po(u,v):
    return all(a <= b for a, b in zip(u,v))
def le_po(u,v):
    return leq_po(u,v) and u != v
def list_refines_po(ls):
    return all(not le_po(ls[j], ls[i]) 
               for i in range(len(ls)) for j in range(i+1, len(ls)))

但是，然后给了我某种 O(n²) 复杂度，同时检查列表是否已排序。总订单需要 O(n) 时间。

现在，可能这就是我所期望的：部分订单概括了总订单，所以可能，我应该期望检查更一般的概念具有更差的复杂性。但：

我能比 O(n²) 做得更好吗？

编辑 要尝试，您可以使用以下数据：

ls_in_order     = [(0, 1), (2, 1), (3, 0), (2, 1)]
ls_not_in_order = [(0, 1), (2, 1), (3, 0), (1, 1)]

在这里，没有一对连续的条目ls_not_in_order是降序的，但列表不是按顺序排列的（因为(2,1) ≥ (1,1)）。

标签： pythonalgorithmsorting

解决方案

使用卡恩算法对部分顺序进行排序，在每一步都尝试选择总顺序中的下一个。如果你成功了，那么全序会细化偏序。如果你失败了，那么它不会。

时间将是O(v + e)顶点v的数量，并且e是定义偏序的有向边的数量。

推荐阅读