Sort with respect to multi-level key where the order is different for each level

user_3767239 0
Viewed 138

I have a collection of items with multiple attributes which are represented by tuples:

items = [(a11, a12, ..., a1N), (a21, a22, ..., a2N), ...]

Now I want to sort these items, however the order may vary for each level (e.g. aX1 ascending, aX2 descending, ..., aXN ascending). The crux is that these attributes are not invertible (e.g. text; otherwise the key could be constructed as key=lambda a: (a[0], -a[1], ..., a[N])).

For example with 2-tuples:

items = [('a', 'c'), ('b', 'a'), ('a', 'b'), ('b', 'b'), ('a', 'a')]
reverse = (True, False)  # first level descending, second level ascending

expected = [('b', 'a'), ('b', 'b'), ('a', 'a'), ('a', 'b'), ('a', 'c')]

Other example with 3-tuples:

items = [('a', 'b', 'c'), ('a', 'c', 'b'), ('a', 'b', 'b'), ('b', 'a', 'a'), ('b', 'a', 'b'), ('b', 'b', 'b')]
reverse = (True, False, True)

expected = [('b', 'a', 'b'), ('b', 'a', 'a'), ('b', 'b', 'b'), ('a', 'b', 'c'), ('a', 'b', 'b'), ('a', 'c', 'b')]

I thought about creating a pseudo-inverse, for example via str.translate, but obviously this has its downsides too, as one needs to keep track of all the edge cases.

python-3.x sorting python string
4 Answers

Assuming all items in the tuple are string characters, you can encode them into hex string where a character c will be set to be format(ord(c), 'x') if reverse is not True and format(127 - order(c), 'x') if reverse is True. Now that you have the encoded string of the tuple, you can perform the regular string sorting using sorted

items = [('a', 'b', 'c'), ('a', 'c', 'b'), ('a', 'b', 'b'), ('b', 'a', 'a'), ('b', 'a', 'b'), ('b', 'b', 'b')]
reverse = (True, False, True)

items_sorted = sorted(items, key = lambda x: "".join([format(127 - ord(x[i]), "x") if reverse[i] else format(ord(x[i]), "x") for i in range(len(x))]))
user_73753470

Here's a solution which applies the reverse as -1 and 1 for True and False respectively, to the ordinaled version of each attribute - since it's likely that string attributes are more than one character. The idea was to create a key function that can be passed to sorted().

Edit: Here's the version with multilevel_order applying different reversal rules (note the name change):

def multilevel_order(reverse):
    multipliers = tuple(-1 if trufal else 1 for trufal in reverse)

    def key_func(item):
        return tuple(tuple(map(m.__mul__, map(ord, attr))) for attr, m in zip(item, multipliers))

    return key_func

Results:

items = [('a', 'b', 'c'), ('a', 'c', 'b'), ('a', 'b', 'b'),
         ('b', 'a', 'a'), ('b', 'a', 'b'), ('b', 'b', 'b')]
reverse = (True, False, True)
expected = [('b', 'a', 'b'), ('b', 'a', 'a'), ('b', 'b', 'b'),
            ('a', 'b', 'c'), ('a', 'b', 'b'), ('a', 'c', 'b')]

print(sorted(items, key=multilevel_order(reverse)) == expected)
# True

items = [('a', 'c'), ('b', 'a'), ('a', 'b'), ('b', 'b'), ('a', 'a')]
reverse = (True, False)  # first level descending, second level ascending
expected = [('b', 'a'), ('b', 'b'), ('a', 'a'), ('a', 'b'), ('a', 'c')]

print(sorted(items, key=multilevel_order(reverse)) == expected)
# True

Original answer: I've also used slightly modified values of items to make the effect of ordinaled clearer.

items = [('a', 'bb', 'ccc'), ('a', 'cc', 'bbb'), ('a', 'bb', 'bbb'),
         ('b', 'aa', 'aaa'), ('b', 'aa', 'bbb'), ('b', 'bb', 'bbb')]
reverse = (True, False, True)

multipliers = tuple(-1 if trufal else 1 for trufal in reverse)
def multi_level_key(item):
    ordinaled = (map(ord, attr) for attr in item)
    # this multiplication step could have been included above
    return tuple(tuple(map(m.__mul__, o)) for m, o in zip(multipliers, ordinaled))

Example output of multi_level_key():

[multi_level_key(item) for item in items]
# output:
[((-97,), (98, 98), (-99, -99, -99)),
 ((-97,), (99, 99), (-98, -98, -98)),
 ((-97,), (98, 98), (-98, -98, -98)),
 ((-98,), (97, 97), (-97, -97, -97)),
 ((-98,), (97, 97), (-98, -98, -98)),
 ((-98,), (98, 98), (-98, -98, -98))]

Using that as the key for sorted():

sorted(items, key=multi_level_key)
# output:
[('b', 'aa', 'bbb'),
 ('b', 'aa', 'aaa'),
 ('b', 'bb', 'bbb'),
 ('a', 'bb', 'ccc'),
 ('a', 'bb', 'bbb'),
 ('a', 'cc', 'bbb')]

Potential improvement: I moved multipliers out of the key function so that it's only calculated once. Ideally, that should be put in a closure to multi_level_key() so that it can be used with other reversal rules without needing to write a new function.

user_14317500

Eventually I ended up using the following implementation which uses itertools.groupby to identify ties within already sorted levels and then recursively sorts the corresponding groups. This has the advantage that it fully relies on the builtin string comparison methods.

import itertools as it
import operator as op

def sort_one_level(data, *, reverse, level=0):
    result = sorted(data, reverse=reverse[level])
    if level + 1 < len(reverse):
        result = it.chain.from_iterable(
            sort_one_level(group, reverse=reverse, level=level+1)
            for __, group in it.groupby(result, key=op.itemgetter(level))
        )
    yield from result
user_37672390

Using Reverse Alphabet to invert strings.

Code

from string import printable     # all the printable characters

def tuple_sort(items, rev):
    # Create translation table for printable characters
    trans = str.maketrans(printable, printable[::-1], ' ') 

    # key function forms list with inverted tuple items based upon rev
    return sorted(items, key = lambda item: [s.translate(trans) if flag else s for s, flag in zip(item, rev)])

Test

items = [('a', 'c'), ('b', 'a'), ('a', 'b'), ('b', 'b'), ('a', 'a')]
reverse = (True, False) 
tuple_sort(items, reverse)
# Result: [('b', 'a'), ('b', 'b'), ('a', 'a'), ('a', 'b'), ('a', 'c')]
user_30660770
Related