Sort a list to form the largest possible number

Question

I am trying to write a function that given a list of non negative integers, arranges them such that they form the largest possible number.

For example, given [50, 2, 1, 9], the largest formed number is 95021.

Here is the code that I have tried to solve the problem:

a = [50, 2, 1, 9]
a.sort()
ans = []
for i in range(len(a)-1,-1,-1):
    ans.append(a[i])

print ''.join(map(str,ans))

However, I get 50921 , as 50 is largest, but it should show 9 first.

Answer 1

In Python 2 you can do this with an appropriate comparison function passed to sort.

#!/usr/bin/env python

''' Sort a list of non-negative integers so that
    if the integers were converted to string, concatenated 
    and converted back to int, the resulting int is the highest
    possible for that list

    From http://stackoverflow.com/q/30140796/4014959

    Written by PM 2Ring 2015.05.10

    Python 2 version
'''

data = [
    [50, 2, 1, 9],
    [10, 1],
    [2, 23, 21],
]

def mycmp(a, b):
    a, b = str(a), str(b)
    ab, ba = a + b, b + a
    if ab == ba:
        return 0
    if ab < ba:
        return -1
    return 1

for a in data:
    print 'In: ', a
    a.sort(cmp=mycmp, reverse=True)
    print 'Out:', a
    print

output

In:  [50, 2, 1, 9]
Out: [9, 50, 2, 1]

In:  [10, 1]
Out: [1, 10]

In:  [2, 23, 21]
Out: [23, 2, 21]

---

In Python 3, sort no longer takes a custom comparison function. scpio's answer shows how to use functools to convert a comparison function into a key function, but it's not that hard to do "by hand".

#!/usr/bin/env python

''' Sort a list of non-negative integers so that
    if the integers were converted to string, concatenated 
    and converted back to int, the resulting int is the highest
    possible for that list

    From http://stackoverflow.com/q/30140796/4014959

    Written by PM 2Ring 2015.05.10

    Python 3 compatible version
'''

from __future__ import print_function

class cmpclass(object):
    def __init__(self, n):
        self.n = str(n)

    def __str__(self):
        return self.n

    def _cmp(self, other):
        a, b = self.n, str(other)
        ab, ba = a + b, b + a
        if ab == ba:
            return 0
        if ab < ba:
            return -1
        return 1

    def __lt__(self, other): return self._cmp(other) == -1
    def __le__(self, other): return self._cmp(other) <= 0
    def __eq__(self, other): return self._cmp(other) == 0
    def __ne__(self, other): return self._cmp(other) != 0
    def __gt__(self, other): return self._cmp(other) == 1
    def __ge__(self, other): return self._cmp(other) >= 0


data = [
    [50, 2, 1, 9],
    [10, 1],
    [2, 23, 21],
]

for a in data:
    print('In: ', a)
    a.sort(key=cmpclass, reverse=True)
    print('Out:', a)
    print('')

output

In:  [50, 2, 1, 9]
Out: [9, 50, 2, 1]

In:  [10, 1]
Out: [1, 10]

In:  [2, 23, 21]
Out: [23, 2, 21]

The previous Python 3 compatible version I posted doesn't actually work on Python 3 :oops:! That's because the __cmp__ method is no longer supported in Python 3. So I've changed my old __cmp__ method to _cmp and used it to implement all 6 of the rich comparison methods.

Important note

I have to mention that this comparison function is a bit weird: it's non-transitive, in other words, a>b and b>c doesn't necessarily imply a>c. And that means that the results of using it in .sort() are unpredictable. It does appear to do the right thing for the data I've tested it with, eg, it returns the correct result for all permutations of [1, 5, 10], but I guess it really shouldn't be trusted to do so for all input.

An alternative strategy that's guaranteed to work is brute force: generate all permutations of the input list & find the permutation that yields the maximum result. But hopefully there's a more efficient algorithm, since generating all permutations of a large list is rather slow.

---

As Antti Haapala points out in the comments, my old comparison functions were unstable when comparing different numbers that consist of the same sequences of repeating digits, eg 123123 and 123123123. Such sequences should compare equal, my old functions didn't do that. The latest modification addresses that problem.

---

Update

It turns out that mycmp() / _cmp() actually is transitive. It's also stable, now that it handles the ab == ba case properly, so it's safe to use with TimSort (or any other sorting algorithm). And it can be shown that it gives the same result as Antti Haapala's fractionalize() key function.

In what follows I'll use uppercase letters to represent integers in the list and I'll use the lowercase version of a letter to represent the number of digits in that integer. Eg, a is the number of digits in A. I'll use _ as an infix operator to represent digit concatenation. Eg, A_B is int(str(A)+str(B); note that A_B has a+b digits. Arithmetically,
A_B = A * 10**b + B.

For the sake of brevity, I'll use f() to represent Antti Haapala's fractionalize() key function. Note that f(A) = A / (10**a - 1).

Now for some algebra. I'll put it in a code block to keep the formatting simple.

Let A_B = B_A
A * 10**b + B = B * 10**a + A
A * 10**b - A = B * 10**a - B
A * (10**b - 1) = B * (10**a - 1)
A / (10**a - 1) = B / (10**b - 1)
f(A) = f(B)

So A_B = B_A if & only if f(A) = f(B)

Similarly,
A_B > B_A if & only if f(A) > f(B)
This proves that using mycmp() / _cmp() as the sort comparison function
is equivalent to using fractionalize() as the sort key function.

Note that
f(A_B) = (A * 10**b + B) / (10**(a+b)-1)
and
f(B_A) = (B * 10**a + A) / (10**(a+b)-1)

So f(A_B) = f(B_A) iff A_B = B_A, and f(A_B) > f(B_A) iff A_B > B_A

Let's see what happens with 3 integers.

f(A), f(B), f(C) are just real numbers, so comparing them is
transitive. 
And so if f(A) > f(B) and f(B) > f(C) then f(A) > f(C). 
This proves that mycmp() / _cmp() is also transitive.

Clearly, if f(A) > f(B) > f(C) then
A_B > B_A, B_C > C_B, A_C > C_A

Let B_C > C_B
For any A,
A * 10**(b+c) + B_C > A * 10**(b+c) + C_B
So A_B_C > A_C_B
i.e. adding the same integer to the beginning of B_C and C_B preserves
the inequality.

Let A_B > B_A
For any C,
(A_B) * 10**c + C > (B_A) * 10**c + C
So A_B_C > B_A_C,
i.e. adding the same integer to the end of A_B and B_A preserves the
inequality.

Using these results, we can show that
if f(A) > f(B) > f(C) then
A_B_C > A_C_B > C_A_B > C_B_A and
A_B_C > B_A_C > B_C_A > C_B_A.

This covers all 6 permutations of [A, B, C] and shows that A_B_C is the
largest possible integer for that list.

A mathematical induction-style argument shows that sorting a list of any finite length using pairwise comparisons with mycmp() / _cmp() as the comparison function or with fractionalize() as the key function suffices to find the permutation that yields the largest possible integer produced by digit concatenation. The details of this argument will be left as an exercise for the reader. :)

Answer 2

One-liner using insights from Antti Haapala, PM 2Ring and Stefan Pochmann:

from fractions import Fraction
sorted(a, key=lambda n: Fraction(n, 10**len(str(n))-1), reverse=True)

Given a = [50, 5, 51, 59, 2, 1, 9, 98]:

[9, 98, 59, 5, 51, 50, 2, 1]