Python sort a list of lists by occurrence and reversed order

user_12335546 0
Viewed 43

I have the following list

list_55 = [[1,2],[2,1],[3,4],[5,6],[4,3],[1,2],[1,2],[6,5],[6,5]]

I want to sort this list like this. So that the list sorts in an order with descending occurrence and with their reversed list. For example:

[1,2],[1,2],[1,2] followed by [2,1]
[6,5],[6,5] followed by [5,6]
[4,3] followed by [3,4] The order of this last one doesn't matter.

output:

[[1,2],[1,2],[1,2],[2,1],[6,5],[6,5],[5,6],[4,3],[3,4]]

I tried:

sorted(list_55, key=list_55.count, reverse=True)

which gives:

[[1, 2], [1, 2], [1, 2], [6, 5], [6, 5], [2, 1], [3, 4], [5, 6], [4, 3]]

and

sorted(list_55,reverse=True)

gives:

[[6, 5], [6, 5], [5, 6], [4, 3], [3, 4], [2, 1], [1, 2], [1, 2], [1, 2]]

I want a combination of these two. Is there a way to do it?

sorting python
2 Answers

Try:

print(
    sorted(
        list_55,
        key=lambda l: (
            list_55.count(l) + list_55.count(l[::-1]),
            list_55.count(l),
        ),
        reverse=True,
    )
)

Prints:

[[1, 2], [1, 2], [1, 2], [2, 1], [6, 5], [6, 5], [5, 6], [3, 4], [4, 3]]

A little bit more performant solution using :=:

print(
    sorted(
        list_55,
        key=lambda l: (
            (cnt := list_55.count(l)) + list_55.count(l[::-1]),
            cnt,
        ),
        reverse=True,
    )
)

For more performance a version with functools.lru_cache:

from timeit import timeit
from functools import lru_cache
from collections import defaultdict, Counter

list_55 = [
    [1, 2],
    [2, 1],
    [3, 4],
    [5, 6],
    [4, 3],
    [1, 2],
    [1, 2],
    [6, 5],
    [6, 5],
]


def fn1(lst):
    @lru_cache(maxsize=None)
    def key_fn(l):
        cnt = lst.count(l)
        return cnt + lst.count(l[::-1]), cnt

    lst[:] = map(tuple, lst)

    return sorted(
        lst,
        key=key_fn,
        reverse=True,
    )


def fn2(l):
    dct = defaultdict(Counter)
    for lst in l:
        dct[frozenset(lst)].update({tuple(lst): 1})

    # counters_sorted = sorted(
    #     dct.values(), key=lambda c: c.total(), reverse=True
    # )
    counters_sorted = sorted(
        dct.values(), key=lambda c: sum(c.values()), reverse=True
    )  # for python < 3.10

    return [
        tup
        for counter in counters_sorted
        for tup, n in counter.most_common()
        for _ in range(n)
    ]


t1 = timeit(
    "fn1(lst)", setup="lst = list_55 * 1000", number=1, globals=globals()
)

t2 = timeit(
    "fn2(lst)", setup="lst = list_55 * 1000", number=1, globals=globals()
)

print(t1)
print(t2)

Prints (AMD 3700x/Python 3.9):

0.0037845000624656677
0.011112367967143655
user_100359850

Another option is to use collections.Counter, which I guess is more efficient when the input list is long:

from collections import defaultdict, Counter

list_55 = [[1,2],[2,1],[3,4],[5,6],[4,3],[1,2],[1,2],[6,5],[6,5]]

dct = defaultdict(Counter)
for lst in list_55:
    dct[frozenset(lst)].update({tuple(lst): 1})

counters_sorted = sorted(dct.values(), key=lambda c: c.total(), reverse=True)
# counters_sorted = sorted(dct.values(), key=lambda c: sum(c.values()), reverse=True) # for python < 3.10

output = [tup for counter in counters_sorted
              for tup, n in counter.most_common()
              for _ in range(n)]

print(output)
# [(1, 2), (1, 2), (1, 2), (2, 1), (6, 5), (6, 5), (5, 6), (3, 4), (4, 3)]
user_114508200
Related