Need to find. A list of random numbers generated by a user’s input (user defines the length of the list) is given. The task is to create a function that returns a maximum number that is combined from numbers (digits) in the list.

For example, user inputs 3 and the list is [43,76,90]. The maximum number will be 907643.

CodePudding user response：

There are two approaches. Either:

1. Generate all permutations of the list and take the one that generates the largest numbers, or
2. Sort the list of numbers so that for any two elements in the list: int(str(lst[i]) str(lst[j]) > int(str(lst[j]) str(lst[i])) if i < j

Method 2 is used here.

Code

from functools import cmp_to_key

def compare(n1, n2):
    '''
        Compare function to return how numbers generated by:  
             int(str(n1)   str(n2))
                   compares to 
             int(str(n2)   str(n1))
    '''
    forward = int(str(n1)   str(n2))
    reverse = int(str(n2)   str(n1))
    if forward > reverse:
        return -1
    elif forward == reverse:
        return 0
    else:
        return 1
   
def largest_number(lst):
    '''
        Generates largest number from list
    '''
    lst_sorted = sorted(lst, key = cmp_to_key(compare))   # sort list based on compare function
    return int(''.join(str(x) for x in lst_sorted))

Test # Two test cases for t in [[43, 76, 90], [97, 9]]: print(f'{t} -> {largest_number(t)}')

# Output
[43, 76, 90] -> 907643
[97, 9] -> 997

CodePudding user response：

After being informed that my previous answer isn't correct. Here another attempt.

The obvious idea would be to just sort the list using list.sort or sorted with the respective reverse=True flag to get them ordered from highest to lowest and then join them to one number that is then converted to an int.

The pitfall is apparently that short high numbers could end up being better suited for a leading position then numbers that are generally bigger, like [3, 21] would result in 213 while 321 is the better option.

Now what you could do is simply to pad each number with trailing 9's till they reach the length of the longest number. For example you can convert them to strings and measure the length and then add 9's till they have that length. That way 399 > 219 and therefore the 3 would take the leading position.

All you need to do then is to sort the two lists (the padded and the original at the same time). Here's an example of how that could be done:

import more_itertools as mit


name = ["Megan", "Harriet", "Henry", "Beth", "George"]
score_list = [9, 6, 5, 6, 10]
    
mit.sort_together([name, score_list])
# [('Beth', 'George', 'Harriet', 'Henry', 'Megan'), (6, 10, 6, 5, 9)]

Which I've copied from here: How to sort a list according to another list? Python

That should be enough of a sketch of an algorithm and this time it should work.