pythonlistsorting

How to group elements in a list?

I have a python list: 

['AM43',
 'AM22',
 'AM51',
 'AM43',
 'AM22',
 'AM51',
 'AM43',
 'AM22',
 'AM51']

I want the output to be a list:

['AM43',
 'AM43',
 'AM43',
 'AM22',
 'AM22',
 'AM22',
 'AM51',
 'AM51',
 'AM51']

I tried sort() but that also rearranges the order. I don't want that. I want the output to be in the same order as the input list.

Solution

  • You can create a dict that stores the index of the first occurrence of each value, and use the dict to perform the sort:

    lst = ["AM43", "AM22", "AM51", "AM43", "AM22", "AM51", "AM43", "AM22", "AM51"]

ix = {k: i for i, k in reversed(list(enumerate(lst)))}
res = sorted(lst, key=ix.get)
# ['AM51', 'AM51', 'AM51', 'AM22', 'AM22', 'AM22', 'AM43', 'AM43', 'AM43']

    Edit: @emsimposon92 provides a 2-pass linear-time solution implementable as follows:

    from collections import Counter

ctr = Counter(lst)
visited = set()
res2 = list()
for x in lst:
    if x in visited:
        continue
    res2.extend([x] * ctr[x])
    visited.add(x)