Checking compatible total orders given by a Python list

I'm using the IPython shell here.

Suppose I have two lists

In [1]: L1 = [1,3,4,5,2]

In [2]: L2 = [1,3,5,5,1]

I'd like to say that L1 and L2 are compatible in the sense that the ordering generated by the indices of the increasing order of the elements are compatible.

That is, L1 gives 0<4<1<2<3 while L2 gives {0,4}<1<{2,3}. (If stackoverflow accepted jsmath or MathJax, this would be easier, my apologies.)

Edit: As pointed out below, this is not exactly checking whether two given elements are < or <= in both of these. I like @Cosmologicon's example that [1,2] and [1,1] are compatible, as are [1,1] and [2,1], but [2,1] and [1,2] are not. I hope this clarifies what I mean.

So I'd like a way to take two lists and check that the (not necessarily strict) total orders given by those two lists are compatible like this. Here is an example where they are not.

In [3]: L3 = [1,2,3,4,5]

In [4]: L4 = [1,2,4,2,5]

I hope it is clear the order given by L3 is 0<1<2<3<4; the order given by L4 is 0<{1,3}<2<4, and the incompatibility is that while 1<=3 in both orders, 2<3 in one of the while 3<2 in the other.

Another, harder, example is whether [1,3,5,5,1] and [1,2,2,3,2] are compatible. The non-strict total orders are {0,4}<1<{2,3} and 0<{1,2,4}<3

It would suffice for my purposes to restrict to the case where the biggest number is always len(list1) and the only possible values are integers from 1 to len(list1) and where list1 always is some permutation of that set of integers, but naturally I wouldn't complain if someone found something more general. Thanks 开发者_开发知识库very much in advance!

Disclaimer from a first-time poster: This is not a question about sorting :) I did do quite a bit of searching for this, but really only found more programming-type questions, which are nearly always about sorting or comparing values; this is a little more subtle. In fact, it's really a mathematical application, so it may not seem as 'useful' to many folks here, though it will be quite useful to me. At any rate, it's beyond my current skill level to hack this out very quickly, though I hope someday it will be 'obvious' to me. I don't think there is anything in itertools for this, either, though I'd love to be proven wrong.

Part of the way there would be to generate a list of tuples of list-elements and indexes, I think. This can then be sorted by list-element value and the index extracted.

Something like:

L1order = [t[1] for t in sorted(zip(L1, range(len(L1))))]
L2order = [t[1] for t in sorted(zip(L2, range(len(L2))))]
L1order == L2order

Turning this into a function should be trivial.

I did the following expanding on shang's answer. It takes into consideration the special fact involved when two values are the same. Simply ordering the lists and comparing them could give the wrong result. For example, if the order in list 1 is 0 < 1 < 2 and the order in list 2 is 0 < 1 <= 2, ordering the second list could give as result both [0,1,2] and [0,2,1], and in this last case, shang's method would fail. This depends on the behavior of the sorting routine.

import operator

def order_indexes(l):
    tmp = list(enumerate(l))
    tmp.sort(key=operator.itemgetter(1))
    return map(operator.itemgetter(0), tmp)

def are_compatible(l1, l2):
    # Order one list, retaining the indexes
    ordered = order_indexes(l1)
    # For each pair of indexes on the list
    for i in xrange(len(ordered) - 1):
        pair = (ordered[i], ordered[i + 1])
        # See if the pairs in the other list are compatible
        # If a1 <= b1 then a2 must be <= b2 
        if l2[pair[0]] > l2[pair[1]]:
            return False
    # If all pairs are compatible, then the lists are compatible
    return True

if __name__ == '__main__':
    l1 = [1,3,4,5,2]
    l2 = [1,3,5,5,1]
    l3 = [1,2,3,4,5]
    l4 = [1,2,4,2,5]
    print "L1 X L2 ",are_compatible(l1, l2)
    print "L2 X L1 ",are_compatible(l2, l1)
    print "L3 X L4 ",are_compatible(l3, l4)
    print "L4 X L3 ",are_compatible(l4, l3)

I'm not 100% sure if this is what you are after, but it works for the examples you have provided:

import operator

def compatible(l1,l2):
    return ordered_indices(l1) == ordered_indices(l2)

def ordered_indices(l):
    tmp = list(enumerate(l))
    tmp.sort(key=operator.itemgetter(1))
    return map(operator.itemgetter(0), tmp)

>>> compatible([1,3,4,5,2], [1,3,5,5,1])
True
>>> compatible([1,2,3,4,5], [1,2,4,2,5])
False

Updated version:

import operator, itertools

def compatible(l1,l2):
    if len(l1) != len(l2): return False
    i1 = ordered_indices(l1)
    i2 = ordered_indices(l2)
    g1 = None
    g2 = None
    while i1 and i2:
        g1 = g1 or i1.pop(0)
        g2 = g2 or i2.pop(0)
        if len(g1) > len(g2):
            g1,g2 = g2,g1
            i1,i2 = i2,i1
        x = g1.pop()
        if x not in g2:
            return False
        g2.remove(x)
    return True


def ordered_indices(l):
    tmp = list(enumerate(l))
    value = operator.itemgetter(1)
    index = operator.itemgetter(0)
    tmp.sort(key=value)
    groups = itertools.groupby(tmp, value)
    return [set(map(index, g)) for k, g in groups]

>>> compatible([1,3,5,5,1],[1,2,2,3,2])
True

That is, L1 gives 0<4<1<2<3 while L2 gives 0<=4<1<2<=3. One can see that if two of these indices are <= each other in one list, that is true in both lists.

Sorry, your definition given here of compatible doesn't match your example. In L2, 4<=0, but the same is not true in L1. I suspect the definition you meant to give is: if a<b in one list, then a<=b in the other list.

In that case, none of the previous solutions work. L1 = [1,1] and L2 = [2,1] should be compatible.

Any solution would need to realize that compatibility is not transitive. For instance, if L1 = [1,2], L2 = [1,1], and L3 = [2,1], then L1 is compatible with L2 and L2 is compatible with L3, but L1 is not compatible with L3. So any solution that checks for equality between some "orderings" computed from the lists will fail.

Thiago Chaves's solution doesn't have this problem, but it fails on L1 = [2,2,1], L2 = [2,1,1]. These should be compatible.

EDIT: If efficiency is not a huge concern, here's a quick O(N^2) solution that simply tests each pair of numbers:

def compat5(L1, L2):
    z = zip(L1, L2)
    return not any(j1<k1 and j2>k2 for j1,j2 in z for k1,k2 in z)

One possible algorithm is as follows:

def compatible
    temp1=L1[:]
    temp2=L2[:]
    max1=max(L1)+1
    max2=max(L2)+2
    order1=[]
    for i in range(len(L1)):
        pos=t1.index(min(t1))
        order1.append(pos)
        t1[pos]=max1
    for i in range(len(L2)):
        pos=t2.index(min(t2))
        order2.append(pos)
        t2[pos]=max2
    return order1==order2

This algorithm relies on the members of each list being unequal. If you want to use lists with duplicates, you would need to keep track of the pairs that are equal and check whether switching any of the pairs would make the orderings the same.

[EDIT] Ok, I'm stupid. It can be made even simpler, obviously:

def compatible_ordering(xs, ys):
    return all(
        y1 <= y2
            for (_, y1), (_, y2) in pairwise(sorted(izip(xs, ys)))
    )

[/EDIT]

Here's an O(n * log n) solution:

from itertools import izip, tee

def pairwise(iterable):
    a, b = tee(iterable)
    next(b)
    return izip(a, b)

def compatible_ordering(xs, ys):
    return all(
        x1 == x2 or y1 <= y2
            for (x1, y1), (x2, y2) in pairwise(sorted(izip(xs, ys)))
    )

It's basically a one liner, if you don't count the pairwise() recipe from itertools. Man, you gotta love Python for this.

BTW, notice the similarity to the wrong solution at the end.

How it works can probably be easier explained if we rewrite the algorithm into a more procedural form:

def compatible_ordering(xs, ys):             # line 0
    xys = zip(xs, ys)                        # line 1
    xys.sort()                               # line 2
    for (x1, y1), (x2, y2) in pairwise(xys): # line 3
        if x1 < x2 and y1 > y2:              # line 4
            return False                     # line 5
    return True                              # line 6

This time we don't try to find out if a condition holds for all elements ( = success), but instead if a condition holds for some element ( = failure), so the testing formula is basically negated.

Now, for every pair of neighbouring tuples ((x1, y1), (x2, y2)):

• Always x1 <= x2, since we sorted them that way. That implies that if x1 != x2 then x1 < x2.

• If x1 == x2 we know that y1 <= y2, again because we sorted them so.

• If x1 < x2 and y1 <= y2, both (x1, x2) and (y1, y2) have the same ordering and we continue.

• Otherwise if x1 < x2 and y1 > y2, our two lists have incompatible orderings and we return False.

• If we're done iterating and haven't found any incompatibility, we return True.

IOW: the sorting creates an ordering for ys defined by xs, and by ysitself for equal elements in xs (since equal elements of xs don't impose any ordering on ys). Then all we have to do is to test if ys is indeed ordered.

Here's an example. After line 0 we have e.g.:

xs == [4, 3, 4, 2, 5, 4, 0, 2, 0, 5]
ys == [4, 1, 5, 1, 5, 5, 2, 2, 1, 3]

In line 2 we zip those and get:

xys == [(4, 4), (3, 1), (4, 5), (2, 1), (5, 5), (4, 5), (0, 2), (2, 2), (0, 1), (5, 3)]

In line 3 we sort:

xys == [(0, 1), (0, 2), (2, 1), (2, 2), (3, 1), (4, 4), (4, 5), (4, 5), (5, 3), (5, 5)]

In line 4 we iterate through all pairs of neighbouring tuples of the sorted list and test in line 5:

  x1  y1     x2  y2       x1     x2      y1    y2
( 0 , 1 ), ( 0 , 2 )  -->  0  <  0  and  1  >  2   -->  False  -->  continue
( 0 , 2 ), ( 2 , 1 )  -->  0  <  2  and  2  >  1   -->  True   -->  return False

BTW #2: It's very possible that this version is faster then the oneliner.

[EDIT]

The following was my first and WRONG answer to the OP's question. Still, I don't delete it, as an example to what happens if you post without reading carefully.

Here's an O(n) solution:

def compatible_ordering(xs, ys):
    return all(
        (x1 <= x2) == (y1 <= y2)
            for (x1, x2), (y1, y2) in izip(pairwise(xs), pairwise(ys))
    )