Efficiently sort list by sequence

Question

Lets say i have two lists:

sequence = [25, 15, 20, 15, 25, 25]
l = [(25, 'banana'), 
     (25, 'apple'), 
     (25, 'pine'), 
     (20, 'soap'), 
     (15, 'rug'), 
     (15, 'cloud')]

I would like to sort the second list l in the order of sequence. In the example the number 25 appears multiple times, in this case it doesn't matter which tuple is in the place as long as it has the value 25. The lists will always be of the same length.

My current approach is this:

r = list(range(len(sequence)))

for i, v in enumerate(sequence):
    for e in l:
        if e[0] == v:
            r[i] = e
            l.remove(e)
print(r)

Possible Output:

[(25, 'banana'), (15, 'rug'), (20, 'soap'), (15, 'cloud') (25, 'apple'), (25, 'pine')]

Do you see a better way to do this?

Thanks for your help!

Muff

Answer 1

Yes. First create a default dictonary with number as key, and names as values of each key (as a list)

sequence = [25, 15, 20, 15, 25, 25]
l = [(25, 'banana'),
     (25, 'apple'),
     (25, 'pine'),
     (20, 'soap'),
     (15, 'rug'),
     (15, 'cloud')]

from collections import defaultdict

d = defaultdict(list)
for i,n in l:
    d[i].append(n)

then, iterate on the sequence and remove from relevant list (matching number) using list.pop to remove one item at a time (there must be enough items in each list and the keys must be there, or you'll get a python exception (empty list/key error)):

result = [(i,d[i].pop()) for i in sequence]
print(result)

result:

[(25, 'pine'), (15, 'cloud'), (20, 'soap'), (15, 'rug'), (25, 'apple'), (25, 'banana')]

the order is different from the expected output, but the numbers match the names, and that's the point. If you want the same order just remove first item instead (less performant in lists, so if you have the choice, better insert & remove items in a list by the last one, it's faster):

result = [(i,d[i].pop(0)) for i in sequence]

gives:

[(25, 'banana'), (15, 'rug'), (20, 'soap'), (15, 'cloud'), (25, 'apple'), (25, 'pine')]