Sort a list with duplicates based on another list with same items but different order

user_13860719 0
Viewed 394

I have two lists of strings like this (two lists have the same items but in different orders):

lst1 = ['C', 'H', 'H', 'H', 'C', 'O', 'O', 'H']
lst2 = ['H', 'H', 'C', 'O', 'H', 'O', 'H', 'C']

To sort lst2 based on lst1, I want to find the lst2 index for each item in lst1. For duplicates I want to take the smallest index that has not been taken.

I want to know the fastest way to get a index list like this:

ids = [2, 0, 1, 4, 7, 3, 5, 6]

then I can sort lst2 by

newlst2 = [lst2[i] for i in ids]

Since there are duplicates, the normal way of getting list indices

ids = [lst2.index(x) for x in lst1]

will give the wrong result

ids = [2, 0, 0, 0, 2, 3, 3, 0]

Any suggestions?

duplicates indexing list sorting python
2 Answers

You could collect each value's indexes and then use those collections. Takes O(n) time.

from collections import defaultdict, deque

indexes = defaultdict(deque)
for i, x in enumerate(lst2):
    indexes[x].append(i)

ids = [indexes[x].popleft() for x in lst1]
user_130084390

Although in theory not the fastest O(n2), for the use case of sorting the position of atoms in molecules, as indicated in the comments (assuming molecules of size of the order of the sample: 10ish atoms), this simple approach, using builtins is probably faster than other more sophisticated answers (O(n)) requiring several imports of external libraries.

You can index each element of lst1 (start) into lst2 (model), and replace the element found in lst2 with None:

start = ['C', 'H', 'H', 'H', 'C', 'O', 'O', 'H']
model = ['H', 'H', 'C', 'O', 'H', 'O', 'H', 'C']

res = []
for elt in start:
    idx = model.index(elt)
    res.append(idx)
    model[idx] = None
    
res   # [2, 0, 1, 4, 7, 3, 5, 6]
user_28755630
Related