How can I use Python3 sort key when the compare function requires the values of the elements being compared?
Below is an example where I used a comparator function, which explicitly requires both elements ( x+y < y+x
) to be present in order to allow comparison. The question is how to write below without using a function cmp_to_key
as key
it only takes one input.
The next problem is the solution to the problem:
Given a list of non-negative integers, arrange them so they make up the largest number.
For example, given the [3, 30, 34, 5, 9]
largest generated 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'
source to share
You can write a custom class that implements __lt__
(a method that implements the comparison <
) in the way you want 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
This should do the same sorting:
>>> sorted([3, 30, 34, 5, 9], key=Comp)
[9, 5, 34, 3, 30]
But I'm not sure if this really gives a "general order" (it might be, I just have some doubts) and if it doesn't, it could lead to unexpected results (in any version of Python, independent of the argument key
or cmp
).
source to share
Just for another way to do it:
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 in the array and make them the same length, repeating as needed. Then you make the lexicographical look. (The numeric sort will be identical at this point, but we want the lines to be executed.)
For example, for [3, 30, 34, 5, 9]
we find that the longest number is 2 digits, so we increase everything to three digits, repeating the digits as needed. These are the keys that are used:
[333, 303, 343, 555, 999]
Then we sort, lower, and collect the result:
[9, 5, 34, 3, 30]
9534330
Intuition starts with "Pick the number with the largest leading digit." The problem arises in what we should do with the tie. For example, why should we choose 3 to 30? The answer is that the largest digit that can appear after 3 is another 3. (If there was a large digit, we would have chosen it already.) So, thinking of 3 as "333333 ...", we we can choose the right one. A similar question: why are we choosing 10 over 100? This makes us realize that the best result after 10 is another number starting with 10. (11 or more we would have chosen already.) So think of it as "10101010 ..." and "100100100100 ...". It turns out that you just need to expand to n * 2 digits, where n is the length of the longest number.
I realize this is a little confusing. I wrote a test to make sure everything is correct. (It is compared to 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 an entrance that doesn't work. I am sure this code is correct.
All that said, I don't know why you don't want to just use it cmp_to_key
. :-)
source to share