Comparing Order of 2 Python Lists

4
votes

I am looking for some help comparing the order of 2 Python lists, list1 and list2, to detect when list2 is out of order.

  • list1 is static and contains the strings a,b,c,d,e,f,g,h,i,j. This is the "correct" order.
  • list2 contains the same strings, but the order and the number of strings may change. (e.g. a,b,f,d,e,g,c,h,i,j or a,b,c,d,e)

I am looking for an efficient way to detect when list2 is our of order by comparing it against list1.

For example, if list2 is a,c,d,e,g,i should return true (as the strings are in order)

While, if list2 is a,d,b,c,e should return false (as string d appears out of order)

6
pythonstringlist
Since list1 is always in alphabetical order, I'm wondering if you need to check list2 against it all. Would it work if you simplied checked if list2 is in alphabetical order of itself? - Darren Haynes

6 Answers

8
votes

First, let's define list1:

>>> list1='a,b,c,d,e,f,g,h,i,j'.split(',')
>>> list1
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']

While your list1 happens to be in alphabetical order, we will not assume that. This code works regardless.

Now, let's create a list2 that is out-of-order:

>>> list2 = 'a,b,f,d,e,g,c,h,i,j'.split(',')
>>> list2
['a', 'b', 'f', 'd', 'e', 'g', 'c', 'h', 'i', 'j']

Here is how to test whether list2 is out of order or not:

>>> list2 == sorted(list2, key=lambda c: list1.index(c))
False

False means out-of-order.

Here is an example that is in order:

>>> list2 = 'a,b,d,e'.split(',')
>>> list2 == sorted(list2, key=lambda c: list1.index(c))
True

True means in-order.

Ignoring elements of list1 not in list2

Let's consider a list2 that has an element not in list1:

>>> list2 = 'a,b,d,d,e,z'.split(',')

To ignore the unwanted element, let's create list2b:

>>> list2b = [c for c in list2 if c in list1]

We can then test as before:

>>> list2b == sorted(list2b, key=lambda c: list1.index(c))
True

Alternative not using sorted

>>> list2b = ['a', 'b', 'd', 'd', 'e']
>>> indices = [list1.index(c) for c in list2b]
>>> all(c <= indices[i+1] for i, c in enumerate(indices[:-1]))
True
3
votes

Why do you need to compare it to list1 since it seems like list1 is in alphabetical order? Can't you do the following?

def is_sorted(alist):
    return alist == sorted(alist)

print is_sorted(['a','c','d','e','g','i'])
# True

print is_sorted(['a','d','b','c','e'])
# False
1
votes

Here's a solution that runs in expected linear time. That isn't too important if list1 is always 10 elements and list2 isn't any longer, but with longer lists, solutions based on index will experience extreme slowdowns.

First, we preprocess list1 so we can quickly find the index of any element. (If we have multiple list2s, we can do this once and then use the preprocessed output to quickly determine whether multiple list2s are sorted):

list1_indices = {item: i for i, item in enumerate(list1)}

Then, we check whether each element of list2 has a lower index in list1 than the next element of list2:

is_sorted = all(list1_indices[x] < list1_indices[y] for x, y in zip(list2, list2[1:]))

We can do better with itertools.izip and itertools.islice to avoid materializing the whole zip list, letting us save a substantial amount of work if we detect that list2 is out of order early in the list:

# On Python 3, we can just use zip. islice is still needed, though.
from itertools import izip, islice
is_sorted = all(list1_indices[x] < list1_indices[y]
                for x, y in izip(list2, islice(list2, 1, None)))
0
votes
is_sorted = not any(list1.index(list2[i]) > list1.index(list2[i+1]) for i in range(len(list2)-1))

The function any returns true if any of the items in an iterable are true. I combined this with a generator expression that loops through all the values of list2 and makes sure they're in order according to list1.

0
votes
if list2 == sorted(list2,key=lambda element:list1.index(element)):
    print('sorted')
0
votes

Let's assume that when you are writing that list1 is strings a,b,c,d,e,f,g,h,i that this means that a could be 'zebra' and string b could actually be 'elephant' so the order may not be alphabetical. Also, this approach will return false if an item is in list2 but not in list1.

good_list2 = ['a','c','d','e','g','i']

bad_list2 = ['a','d','b','c','e']

def verify(somelist):
    list1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
    while len(list1) > 0:
        try:
            list1 = list1[:list1.index(somelist.pop())]
        except ValueError:
            return False
    return True