priority_sort.py

import collections


def sort_by_frequency_with_original_order_fake(_list):
    """
    1. Sortd by frequency at first;
    2. When some items have the same frequency, follow the original order. (failed!!!)
    """
    counter = collections.Counter(_list)
    _counter = sorted(counter.items(), key=lambda t: t[1], reverse=True)
    return _counter


def sort_by_frequency_with_original_order(_list):
    """
    1. Sortd by frequency at first;
    2. When some items have the same frequency, follow the original order.

    python iterable.sort method is guaranteed to be stable.
    Refs:
    http://stackoverflow.com/a/34052163/620953
    https://docs.python.org/2/library/stdtypes.html#mutable-sequence-types (note 9)
    """
    items = []
    for item in _list:
        if item not in items:
            items.append(item)
    items_with_count = [(item, _list.count(item)) for item in items]
    items = sorted(items_with_count, key=lambda t: t[1], reverse=True)
    return [t[0] for t in items]

if __name__ == "__main__":
    case = ['a', 'b', 'b']
    assert ['b', 'a'] == sort_by_frequency_with_original_order(case)

    case = ['a', 'c', 'b']
    assert ['a', 'c', 'b'] == sort_by_frequency_with_original_order(case)

    case = ['a', 'c', 'b', 'c']
    assert ['c', 'a', 'b'] == sort_by_frequency_with_original_order(case)