CODEWITHSUNDEEP
pythonpython-2.7listsorting
Muhammad Usman Arif
Muhammad Usman Arif

Reputation: 23

sorting list of list w.r.t another list of lists in python

I have two list of lists, where i want to sort the first with respect to the second. For example here i have the two

old = [[1, 7, 3, 2, 5, 4, 6, 0, 8, 9], 
       [7, 3, 2, 5, 4, 6, 1, 8, 0, 9], 
       [9, 2, 8, 7, 1, 5, 0, 4, 6, 3]]
new = [[4, 1, 5, 6, 7, 9, 10, 11, 8, 2, 3, 0], 
       [10, 6, 4, 3, 0, 11, 2, 5, 8, 1, 9, 7], 
       [0, 1, 7, 10, 9, 6, 4, 5, 8, 2, 3, 11]]

I want to sort the new list of list w.r.t the old list of list. so for the new one the entries should become 

sorted_new = [[1, 7, 3, 2, 5, 4, 6, 0, 8, 9, 10, 11], 
              [7, 3, 2, 5, 4, 6, 1, 8, 0, 9, 10, 11], 
              [9, 2, 8, 7, 1, 5, 0, 4, 6, 3, 10, 11]]

important to note is both lists that are to be matched are not of equal size. how can I achieve this?

Upvotes: 0

Views: 71

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477685

You can use the following approach:

sorted_new = []
for sub_new,sub_old in zip(new,old):
    old_idx = {k:v for v,k in enumerate(sub_old)}
    sorted_new.append(sorted(sub_new,key=lambda x:old_idx.get(x,len(sub_old))))

This then generates:

>>> sorted_new
[[1, 7, 3, 2, 5, 4, 6, 0, 8, 9, 10, 11], [7, 3, 2, 5, 4, 6, 1, 8, 0, 9, 10, 11], [9, 2, 8, 7, 1, 5, 0, 4, 6, 3, 10, 11]]

The code works as follows: we first run over the two lists new and old concurrently. For every such pair of lists. We first generate a dictionary, with dictionary comprehension, that maps the elements of the sub_old to their corresponding indices in the list.

Next we construct a sorted list for sub_new. If the element of that sub_new is in the old_idx, we return the index (and this is thus the sorting key). If not, we return a default len(sub_old), which is thus greater than all the indices in the dictionary. As a result that element will be placed at the right of the list.

Since Python's sort function is guaranteed to be stable that means that the elements that were not in old, will maintain the original order.

We could have used some magic around the list.index(..) method, instead of constructing such index dictionary. But the problem with .index(..) is that it runs in O(n). So this would make the algorithm O(m×n log n) for every sublist, with m the number of elements in old, and n the number of elements in new.

Upvotes: 2

Related Questions