How to use Python3 sort key if the compare function requires values of items being compared?

Question

Below is an example, where I've used a comparator function that explicitly requires both the items being present (x+y < y+x) to provide a comparison. The question is how do I write the below without using cmp_to_key function, since key takes only one input.

The following program is a solution to the problem:

Given a list of non-negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

from functors import cmp_to_key

def largestNumber(self, nums):
    numStr = [str(i) for i in nums]

    def str_cmp(x, y):
        if y+x < x+y: return -1
        elif y+x > x+y: return 1
        else: return 0

    numStr.sort(key=cmp_to_key(str_cmp))

    return "".join(numStr).lstrip('0') or '0'

Answer 1

You could write a custom class that implements __lt__ (the method that implements < comparisons) in a way that you need it:

class Comp(object):
    def __init__(self, value):
        self.value = str(value)

    def __lt__(self, other):
        return other.value + self.value <= self.value + other.value

That should produce an identical "sorting":

>>> sorted([3, 30, 34, 5, 9], key=Comp)
[9, 5, 34, 3, 30]

But I'm not sure if that really does provide a "total ordering" (it could, I just have some doubts) and if it doesn't it could actually produce unexpected results (in any Python version independent of key or cmp argument).

Answer 2

Just for another way of doing this:

from itertools import cycle, islice

def extender(n):
    def extend(x):
        s = str(x)
        return "".join(islice(cycle(s), n))
    return extend

def biggest_number(input):
    if (len(input) == 0):
        return 0
    extend = extender(len(str(max(input))) * 2)
    s = sorted(input, key=extend, reverse=True)
    return int("".join(map(str, s)))

Essentially, you take each element of the array and make them the same length by repeating as necessary. Then you do a lexicographical sort. (A numerical sort would be identical at this point, but we want strings when we're done.)

E.g., for [3, 30, 34, 5, 9], we find that the longest number is 2 digits, so we extend everything to be three digits by repeating the digits as needed. These are the keys that get used:

[333, 303, 343, 555, 999]

Then we sort, descending, and assemble the result:

[9, 5, 34, 3, 30]
9534330

The intuition comes from starting with "Pick the number with the biggest leading digit." The issue arises of what we should do with a tie. E.g., why should we pick 3 before 30? The answer is that the biggest digit that could appear after the 3 is another 3. (If there were a bigger digit available, we would have picked it already.) So thinking of the 3 as "333333..." helps us pick the right one. Similar question: why would we pick 10 instead of 100? This leads us to realize that the best result after 10 is another number that starts with 10. (11 or more we would have picked already.) So think of it as "10101010..." and "100100100100...". It turns out, you just need to extend to n*2 digits, where n is the length of the longest number.

I realize that's a bit confusing. I wrote a test to make sure that's all correct. (It compares against your original code.)

from functools import cmp_to_key
import random

def largestNumber(nums):
    numStr = [str(i) for i in nums]

    def str_cmp(x, y):
        if y+x < x+y: return -1
        elif y+x > x+y: return 1
        else: return 0

    numStr.sort(key=cmp_to_key(str_cmp))

    return "".join(numStr).lstrip('0') or '0'

for i in range(1000000):
    input = [random.randint(0, 1000) for _ in range(random.randint(0, 100))]
    if biggest_number(input) != int(largestNumber(input)):
        print("FAILED: {}".format(input))
    if i % 100 == 0:
        print(i)

I have yet to find input that doesn't work. I'm fairly convinced this code is correct.

All of that said, I don't know why you don't want to just use cmp_to_key. :-)