Group list-items by order of appearance in unsorted list

Question

Test cases:

group_ordered([1,3,2,3,6,3,1]) = [1,1,3,3,3,2,6]
group_ordered([1,2,3,4,5,6,1]) = [1,1,2,3,4,5,6]

I have some code already, but it's ugly and probably slow on large lists as well, since for each unique item I'm looking at the whole list. I came up with this algorithm, but I am wondering if there is a faster, cleaner, or more pythonic way I can do this:

def make_order_list(list_in):
    order_list = []
    for item in list_in:
        if item not in order_list:
            order_list.append(item)
    return order_list


def group_ordered(list_in):
    if list_in is None:
        return None
    order_list = make_order_list(list_in)
    current = 0
    for item in order_list:
        search = current + 1
        while True:
            try:
                if list_in[search] != item:
                    search += 1
                else:
                    current += 1
                    list_in[current], list_in[search] = list_in[search], list_in[current]
                    search += 1
            except IndexError:
                break
    return list_in

score 6 · Accepted Answer · answered Jul 09 '15 at 14:13

6

Use a collections.OrderedDict() instance to do the grouping:

from collections import OrderedDict

def group_ordered(list_in):
    result = OrderedDict()
    for value in list_in:
        result.setdefault(value, []).append(value)
    return [v for group in result.values() for v in group]

Because this specialised dictionary object tracks insertion order of the key, the output is ordered by first occurrence of a group value.

Demo:

>>> group_ordered([1,3,2,3,6,3,1])
[1, 1, 3, 3, 3, 2, 6]
>>> group_ordered([1,2,3,4,5,6,1])
[1, 1, 2, 3, 4, 5, 6]

answered Jul 09 '15 at 14:13

Martijn Pieters

1,048,767
296
4,058
3,343

Very nice, thanks! Another way to create the final list would be `list(itertools.chain(*result))` though it is admittedly more cryptic. – wdonahoe Jul 09 '15 at 14:20
@wdonahoe: exactly, which is why I opted for the list comprehension instead. – Martijn Pieters Jul 09 '15 at 14:20
isn't [v for v in (group for group in result.itervalues())] supposed to be similar to [v for group in result.values() for v in group] but i got answer – Ja8zyjits Jul 09 '15 at 14:34
@Ja8zyjits: no, that's just an inefficient way of turning the `result.itervalues()` results into a list, you are not flattening the outcome. – Martijn Pieters Jul 09 '15 at 14:36
sorry thats a typo i meant to say "i got a wrong answer" but dint understand why my answer was wrong – Ja8zyjits Jul 09 '15 at 14:38
is there any possibility to understand what have you done in that comprehension.. i dint understand it – Ja8zyjits Jul 09 '15 at 14:48
@Ja8zyjits: see [nested list comprehensions](http://stackoverflow.com/q/11934468) and [python list comprehension double for](http://stackoverflow.com/q/17657720) – Martijn Pieters Jul 09 '15 at 15:25

Group list-items by order of appearance in unsorted list

1 Answers1