Mr_and_Mrs_D - 6 months ago 4
Python Question

# Sort a subset of a python list to have the same relative order as in other list

So having a list say

`b = [b1, b2, b3]`
I want to be able to sort a list
`a`
in such a way that all
`bi`
's that also exist in
`a`
have the same relative order as in
`b`
- leaving the rest of
`a`
's elements alone. So

``````a = [ b1, x, b3, y, b2] -> [ b1, x, b2, y, b3]
a = [ b1, x, b2, y, b3] -> no change
a = [ b1, x, y, b2]     -> no change
a = [ b3, x, b1, y, b2] -> [ b1, x, b2, y, b3]
``````

b of course may be a tuple or any other ordered structure. What I came up with

``````bslots = dict((x, a.index(x)) for x in a if x in b)
bslotsSorted = sorted(bslots.keys(), key=lambda y: b.index(y))
indexes = sorted(bslots.values())
for x,y in zip(bslotsSorted, indexes):
a[y] = x
``````

is clumsy and O(n^2)

• First create a dictionary using items from `b` where the key is the item and value is its index, we will use this to sort the matched items in `a` later on.

• Now filter out item from `a` that are present in that dict, dict provides O(1) lookup.

• Now sort this list of filtered items and convert it to an iterator.

• Now loop over `a` again and for each item check if is present in dict then fetch its value from iterator otherwise use it as is.

``````def solve(a, b):
dct = {x: i for i, x in enumerate(b)}
items_in_a = [x for x in a if x in dct]
items_in_a.sort(key=dct.get)
it = iter(items_in_a)
return [next(it) if x in dct else x for x in a]
...
>>> b = ['b1', 'b2', 'b3']
>>> a = [ 'b1', 'x', 'b3', 'y', 'b2']
>>> solve(a, b)
['b1', 'x', 'b2', 'y', 'b3']
>>> a = [ 'b1', 'x', 'b2', 'y', 'b3']
>>> solve(a, b)
['b1', 'x', 'b2', 'y', 'b3']
>>> a = [ 'b1', 'x', 'y', 'b2']
>>> solve(a, b)
['b1', 'x', 'y', 'b2']
>>> a = [ 'b3', 'x', 'b1', 'y', 'b2']
>>> solve(a, b)
['b1', 'x', 'b2', 'y', 'b3']
``````

Overall time complexity is going to be max of `(O(len(a)), O(len(b)), O(items_in_a_length log items_in_a_length)`.