Check if a total order refines a partial order

user_9484595 0
Viewed 94

Consider pairs (x,y) of integers. We impose a partial order such that (x,y) ≤ (x',y') wrt. that partial order of x ≤ x' and y ≤ y'. If neither (x,y) ≤ (x',y') nor (x',y') ≤ (x,y), we say that (x,y) and (x',y') are incomparable.

Now, I have a list ls of such pairs. I want to check that the order of that list refines the partial order defined above; i.e., I need to check that to the right of any element in the list, there come no smaller elements.

Of course I could do the following:

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)))

However, then gives me some kind of O(n²)-complexity, while checking that a list is sorted wrt. total order takes O(n)-time.

Now, probably, that's what I've got to expect: partial orders generalise total orders, so probably, I should expect that checking the more general notion has a worse complexity. But:

Can I do better than O(n²)?

Edit To try, you can use the following data:

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

Here, no pair of consecutive entries in ls_not_in_order is descending, but the list is not in order (because (2,1) ≥ (1,1)).

sorting algorithm python
2 Answers

Use Kahn's algorithm to sort the partial order, at every step trying to choose what is next in the total order. If you succeed, then the total order refines the partial order. If you fail, then it does not.

The time will be O(v + e) where v is the number of vertices, and e is the number of directed edges that define the partial order.

user_5854110

You can do this in O(n log n) time using a balanced BST, plus an auxiliary doubly linked list of predecessors/successors for that BST.

The idea is to iterate through the points in the total order, maintaining a data structure that can tell you in log n time whether we've seen a point whose x and y values are at least as large as our current point. We'll keep an ordered sequence of points (p1, p2, ... pk) whose x-values are increasing and y-values are decreasing, forming a kind of diagonal down-and-right stepped line. To add a point P = (x,y) (ignoring ties for now), do a binary search based on x, and insert P into the BST and into the linked list so that x-values are still increasing.

If you let P.left and P.right denote the predecessor and successor of point P in our sequence, we can check whether P caused an order violation by testing whether P.right.y >= P.y: If so, because P.right has a higher-or-equal x-value and higher-or-equal y-value, this violates the partial order (again, ignoring exact ties for now). Otherwise, to maintain the decreasing order of y-values, we repeatedly delete P.left from the tree and our list as long as P.left.y <= P.y. In total, this takes n log n time, since we ultimately perform at most one search, insertion, or deletion on every node, but some steps may take longer than others.

To deal with tied values of x, if the value of y is tied as well, we only check for partial order violations, and don't change the tree or list (and don't insert a copy of P). If the value of P.y is smaller than the old point's y, there is a violation. Otherwise, delete the old point and check for violations/update the tree like normal.

user_167571740
Related