CODEWITHSUNDEEP
pythonpython-3.xsortingcomparator
m0etaz
m0etaz

Reputation: 1003

Can this comparator function be replaced with an equivalent key function?

Let's say I have a comparator that uses both values of the comparison to decide a sort.

For example, in this problem we have to use a comparator function that uses both elements:

def comparator(a, b): 
    ab = str(a) + str(b) 
    ba = str(b) + str(a) 
    return ((int(ba) > int(ab)) - (int(ba) < int(ab)))

Can this be written in the key=lambda x: ... format when sorting?

I'm aware that a cmp_to_key function exists to convert cmp functions to key functions. My question is whether we can write it as a key function without having to convert it that way.

Upvotes: 5

Views: 282

Answers (1)

kaya3
kaya3

Reputation: 51034

Since you've ruled out solutions that work like functools.cmp_to_key (i.e. declaring a class with dunder comparison methods), I infer that you want a way to do this where the key function only uses built-in types.

The problem is that logically, the key for a number like 25 is the infinite sequence (2, 5, 2, 5, ...). The reason you need an infinite sequence is that you could always come across a number like 252525252525253, where the result of the comparison depends on the last digit because the rest of the digits are that repeated sequence from the other number.

If you have a bound on the size of the input numbers (say we know they're all at most 10 digits), then the sequence only needs to be repeated up to 10 digits length, and then lexicographic comparison (e.g. of strings or tuples) will work:

def key_func(n, digits=10):
    s = str(n)
    return (s * digits)[:digits]

As Stefan Pochmann points out, however, there is a built-in type Fraction which can be used to represent an infinite repeating sequence of digits: for example, (2, 5, 2, 5, ...) is represented as Fraction(25, 99) since its decimal expansion is 0.2525.... Comparing fractions is equivalent to comparing their decimal expansions lexicographically:

from fractions import Fraction

def key_func(n):
    k = len(str(n))
    return Fraction(n, 10**k - 1)

Examples (same for both key functions):

>>> sorted([54, 546, 548, 60], key=key_func)
[54, 546, 548, 60]
>>> sorted([1, 34, 3, 98, 9, 76, 45, 4], key=key_func)
[1, 3, 34, 4, 45, 76, 98, 9]
>>> sorted([25, 252525251], key=key_func)
[252525251, 25]
>>> sorted([25, 252525253], key=key_func)
[25, 252525253]

The resulting lists should be joined in reverse order to produce the largest possible number by concatenation, so e.g. [54, 546, 548, 60] maps to 6054854654.

Upvotes: 3

Related Questions