Sort a list of lists with duplication constraint-CodePudding

I have a list where in each sub list the first element represents a product and the second a price:

my_list = [['a',100],['b',100],['a',75],['c',120],['a',400],['c',150]]

I want to sort by the price descending, but I want a product to repeat only after one of each product has already been seen. In the example I have three distinct products: 'a', 'b', 'c' The ordering would then be:

sorted_list = [['a',400],['c',150],['b',100],['c',120],['a',100],['a',75]]

Is this possible in one pass?

CodePudding user response：

Group by product, sort each product list separately, then interleave the lists.

Grouping is typically done with a dict of lists. Interleaving can be done with itertools.zip_longest.

from itertools import chain, zip_longest
from operator import itemgetter

def interleave_sort(l, marker="__dummyvalue__"):
    # GROUPING
    groups = {}
    for product, price in l:
        groups.setdefault(product, []).append(price)
    for product_list in groups.values():
        product_list.sort(reverse=True)
    sublists = ([[product, price] for price in prices] for product, prices in groups.items())
    # INTERLEAVING
    _marker = (marker, 0)
    i = chain.from_iterable(sorted(r, key=itemgetter(1), reverse=True) for r in zip_longest(*sublists, fillvalue=_marker))
    return (x for x in i if x is not _marker)

print(list(interleave_sort([['a',100],['b',100],['a',75],['c',120],['a',400],['c',150]])))
# [['a', 400], ['c', 150], ['b', 100], ['c', 120], ['a', 100], ['a', 75]]

print(list(interleave_sort([['a', 2], ['a', 2], ['a', 2], ['b', 1], ['b', 1], ['b', 1], ['c', 0], ['c', 0], ['c', 0]])))
# [['a', 2], ['b', 1], ['c', 0], ['a', 2], ['b', 1], ['c', 0], ['a', 2], ['b', 1], ['c', 0]]

Note that the last two lines, i = ... and return..., are adapted from the source code of more_itertools.interleave_longest. I just added an extra sorted(...) in there to fit your requirements.