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

Question

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?

But it is not really clear to me what you mean with "with respect to another list". Especially since the lists are not of equal size. Can you explain how the input maps on the output? — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Jul 21, 2017 at 10:30
Based on you example you do not sort the list, you simply append the list new with elements of old that were not in the list yet. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Jul 21, 2017 at 10:32
To me this question is completely unclear. It seems the "sorted new" is not sorted at all? — Jonas Adler
– Jonas Adler, Commented Jul 21, 2017 at 11:01

willeM_ Van Onsem · Accepted Answer · 2017-07-21 10:53:06Z

2

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.

edited Jul 21, 2017 at 10:53

answered Jul 21, 2017 at 10:36

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Muhammad Usman Arif Over a year ago

Exactly what I wanted to do. Thanks a lot :)

Collectives™ on Stack Overflow

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

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related