form the largest number possible in a list [duplicate]

Question

Given a list such as: [3, 30, 34, 5, 9]. Output: 9534330 Write a program to return the largest number possible

In my code I have used permutation here:

from itertools import permutations
x = [3, 30, 34, 5, 9]
y = permutations(x)
n = len(y)
e = []
for i in y:
    a = map(str, i)
    e.append(int("".join(i)))
print "Largest Number {}".format(sorted(e)[-1])

Here n which is the length of the number of permutations is 120 because of 5!. Is there a better way to solve this problem?

Answer 1

Sorting all numbers in descending order is the simplest solution that occurs to us. But this doesn’t work.

For example, 548 is greater than 60, but in the output, 60 comes before 548. As a second example, 98 is greater than 9, but 9 comes before 98 in the output.

The solution is to use any comparison based sorting algorithm. Thus, instead of using the default comparison, write a comparison function myCompare() and use it to sort numbers.

Given two numbers X and Y, how should myCompare() decide which number to put first – we compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y).

If XY is larger, then, in the output, X should come before Y, else Y should come before X.

For example, let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542. Since 60542 is greater than 54260, we put Y first.

Calculating Permutations yield a higher time complexity. A better solution in python would be:

def largestNumber(A):
    maxlen = len(str(max(A)))
    if all(v == 0 for v in A):
        return '0'
    return ''.join(sorted((str(v) for v in A), reverse=True,
                      key=lambda i: i*(maxlen * 2 // len(i))))

largestNumber([3, 30, 34, 5, 9])

Answer 2

The solution to this problem leads to an interesting transformation that is worth explaining.

Assume we want to know which of XY or YX is larger for given X and Y. Numerically, we want the largest of X.10^y + Y and Y.10^x + X, where the lowercase denote the number of digits of the uppercase variables.

Then with a little math, the comparison

X.10^y + Y < Y.10^x + X

can be rewritten

X / (10^x - 1) < Y / (10^y - 1)

so that XY < YX is certainly a transitive relation and defines a total order. This is very good news because it means that the problem can be reduced to ordinary sorting by using this modified comparison operation.

Now notice that X / (10^x - 1) is a periodic fractional number of the form 0.XXXX..., and to compare 0.XXXX... and 0.YYYY..., it suffices to compare over the longest period. Hence the comparison can work as an ordinary string comparison, except that when the end of the shorter string is reached, we cycle back to the first character.

E.g. 12345 > 12 because 12345 > 12|12|1 and 12105 < 12 because 12105 < 12|12|1.

The comparison function can be described as follows:

def Cmp(X, Y):
    l= max(len(X), len(Y))
    for i in range(l):
        if X[i % len(X)] < Y[i % len(Y)]:
            return 1 # X > Y
        elif X[i % len(X)] > Y[i % len(Y)]:
            return -1 # X < Y
    return 0 # X == Y

I don't recommend this particular implementation, which will be slow because of the %.