How to generate the largest number from an input array using Python?-CodePudding

For example the input is [8, 23, 7, 9] --> the output is 98723

Input [865, 1038, 2] --> output 86521038

CodePudding user response：

Sort by the first digit of each number in descending order and concatenate the sorted numbers.

array = [865, 1038, 2]
largest = int(''.join(sorted({str(n): int(str(n)[0]) for n in array}, reverse=True)))
print(largest)

Output:
86521038

CodePudding user response：

You need to find the first digit of each number. You can do that using

int(str(num)[0])

and then sort them by size.

This only works if first digits are different. If not, you will need to look at the next one.

CodePudding user response：

Converting the list of integers to strings and then sorting them is close to the correct answer, and works for the examples in the question. However, as user2357112-supports-monica pointed out, this fails for cases where one number is the prefix of another number, since the longer number is always put first: e.g. [5, 54] becomes 545 not 554. To fix this, we can make a custom comparator that checks for these prefix cases and accounts for them by looking at the first digit after the common prefix and comparing it to the first digit of the numbers, for example, in [5, 54], the 4 is less than 5, so 5 comes before 54, but in [5, 56], 6 is greater than 5 so 56 comes before 5.

Here is some code that implements this:

from functools import cmp_to_key


def largest_combination(input_list):
    strings = [str(x) for x in input_list]

    def compare(a: str, b: str):
        if a == b:  # test for equality first, since every string starts with itself
            return 0
        if a.startswith(b):  # if b is a prefix of a, compare first digit of a after the common prefix with the first digit
            return ord(a[len(b)]) - ord(a[0])
        elif b.startswith(a):  # symmetric case
            return -compare(b, a)
        elif a < b:  # otherwise compare like a normal string
            return -1
        else:
            return 1

    # sort and join together
    combined = ''.join(sorted(strings, key=cmp_to_key(compare), reverse=True))
    # convert to int
    return int(combined)


if __name__ == '__main__':
    print(largest_combination([8, 23, 7, 9]) == 98723)
    print(largest_combination([865, 1038, 2]) == 86521038)
    print(largest_combination([5, 56]) == 565)
    print(largest_combination([5, 54]) == 554)