1

Given an array A of non-negative integers, arrange them such that they form the largest number. example :

 A = [3, 30, 34, 5, 9]
 output : "9534330"

I am able to do this using custom compare function, is it possible to achieve the same using lambda?

Code:

from functools import cmp_to_key

A = list(map(str,A))

def compare(num1,num2):
    if num1 + num2 > num2 + num1:
        return -1           
    else:
        return 1

A = sorted(A,key=cmp_to_key(compare))
return "".join(A)
Stef
  • 13,242
  • 2
  • 17
  • 28
msmd_shafeeq
  • 11
  • 1
  • 4
    This is the one case I know of where it's cleanest to just stick to a comparator function and `functools.cmp_to_key` instead of trying to write a key function by hand. – user2357112 Feb 07 '23 at 07:28
  • 1
    From [cmp_to_key 's documentation](https://docs.python.org/3/library/functools.html#functools.cmp_to_key): *"A comparison function is any callable that accepts two arguments, compares them, and returns a negative number for less-than, zero for equality, or a positive number for greater-than."* So presumably your `compare` function should be rewritten – Stef Feb 07 '23 at 07:30
  • 2
    (Though you really ought to handle the `num1 + num2 == num2 + num1` case in your comparator.) – user2357112 Feb 07 '23 at 07:30
  • It's good to have a well-written question with a good answer here, especially if we expect future duplicates :) – Stef Feb 07 '23 at 07:39
  • In the linked "duplicate" I don't see a single answer that addresses the question of whether it would be possible without cmp_to_key... – Stef Feb 07 '23 at 07:42
  • [This answer](https://stackoverflow.com/a/30189892/12671057) of the duplicate original fits. – Kelly Bundy Feb 07 '23 at 07:43
  • Interesting, although it contains absolutely no explanation for the formula used in the key – Stef Feb 07 '23 at 07:44
  • @Stef Yes, could be better, but it does reference names of people whose answers/comments contain explanations. – Kelly Bundy Feb 07 '23 at 07:45
  • @Stef Why did you say their compare function should be rewritten? – Kelly Bundy Feb 07 '23 at 08:11
  • @Stef I guess because of the `==` case? That's intriguing. My intuition says that if they returned `-1` in that case, it would be safe because that's a stable sort. But now they *swap* "equals", and I'm rather uncertain about that. Might confuse Timsort by giving it conflicting information. – Kelly Bundy Feb 07 '23 at 08:25
  • @KellyBundy The documentation of `cmp_to_key` explicitly states that the compare function should return `0` for two equivalent elements. Currently it returns `1`. So it might or might not work, but that would be implementation dependent. Better to return 0 when we're supposed to return 0. – Stef Feb 07 '23 at 10:17
  • @Stef It would certainly be better. I'm not quite convinced it's necessary. What does "less-than" mean? If we do ascending case-insensitive stable sort and we have the list `['Foo', 'fOo']` and you ask me which of the two strings is smaller, it might be ok to consider `'Foo'` not equal but *smaller*. Not because of its *value*, which equals the other, but because of its *position*. Then again, that requires taking the algorithm into consideration for the comparison. Hmm. When asked to compare two, I won't know which one has the smaller position. Ok ok, I fully agree with you now :-) – Kelly Bundy Feb 07 '23 at 10:45

0 Answers0