Programa de Python para organizar números dados para formar el número más grande

Dada una serie de números, organícelos de manera que produzca el mayor valor. Por ejemplo, si los números dados son {54, 546, 548, 60}, el arreglo 6054854654 da el valor más grande. Y si los números dados son {1, 34, 3, 98, 9, 76, 45, 4}, entonces el arreglo 998764543431 da el mayor valor.

Una solución simple que nos viene a la mente es ordenar todos los números en orden descendente, pero simplemente ordenar no funciona. Por ejemplo, 548 es mayor que 60, pero en la salida 60 viene antes que 548. Como segundo ejemplo, 98 es mayor que 9, pero 9 viene antes que 98 en la salida.

Entonces, ¿cómo lo hacemos? La idea es utilizar cualquier algoritmo de clasificación basado en comparación . 
En el algoritmo de clasificación usado, en lugar de usar la comparación predeterminada, escriba una función de comparación myCompare() y utilícela para ordenar números. 

Dados dos números X e Y , ¿cómo debería myCompare() decidir qué número poner primero? Comparamos dos números XY (Y añadido al final de X) e YX (X añadido al final de Y). Si XY es más grande, entonces X debería aparecer antes que Y en la salida, de lo contrario, Y debería aparecer antes. Por ejemplo, sean X e Y 542 y 60. Para comparar X e Y, comparamos 54260 y 60542. Como 60542 es mayor que 54260, ponemos Y primero.

A continuación se muestra la implementación del enfoque anterior. 
Para mantener el código simple, los números se consideran strings, se usa el vector en lugar de una array normal. 

A continuación se muestra la implementación del enfoque anterior: 

# Python3 Program to get the maximum
# possible integer from given array
# of integers...
  
  
# Custom comparator to sort according
# to the ab, ba as mentioned in description
def comparator(a, b):
    ab = str(a) + str(b)
    ba = str(b) + str(a)
    return ((int(ba) & gt
             int(ab)) -
            (int(ba) & lt
             int(ab)))
  
def myCompare(mycmp):
  
    # Convert a cmp= function into a 
    # key= function
    class K(object):
        def __init__(self, obj, *args):
            self.obj = obj
  
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) & 
                   lt 0
  
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) & 
                   gt 0
  
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
  
        def __le__(self, other):
            return mycmp(self.obj, other.obj) & 
                   lt = 0
  
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) & 
                   gt = 0
  
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K
  
  
# Driver code
if __name__ == "__main__":
    a = [54, 546, 548, 60]
    sorted_array = sorted(a, key = 
                   myCompare(comparator))
    number = "".join([str(i) for i in sorted_array])
    print(number)
  
# This code is Contributed by SaurabhTewary

Producción:

6054854654

Complejidad de tiempo:  O(nlogn), se considera que la clasificación tiene una complejidad de tiempo de ejecución de O(nlogn) y el ciclo for se ejecuta en tiempo O(n).
Espacio Auxiliar: O(1).

Otro enfoque: (usando itertools ) 

Usando la biblioteca incorporada de Python, la biblioteca itertools se puede usar para realizar esta tarea.  

# Python3 implementation this is to 
# use itertools. permutations as 
# coded below:
  
from itertools import permutations
def largest(l):
    lst = []
    for i in permutations(l, len(l)):
  
        # Provides all permutations of the 
        # list values, store them in list to 
        # find max
        lst.append("".join(map(str,i))) 
    return max(lst)
  
print(largest([54, 546, 548, 60])) 
# This code is contributed by Raman Monga

Producción:

6054854654

Complejidad de Tiempo:  O(nlogn)
Espacio Auxiliar: O(1).

Consulte el artículo completo sobre Organizar números dados para formar el número más grande | ¡ Establezca 1 para más detalles!