Construyendo el mayor número posible reorganizando una lista

Digamos que tengo una serie de enteros enteros positivos; Me gustaría manipular el orden para que la concatenación de la matriz resultante sea el mayor número posible. Por ejemplo [97, 9, 13] resulta en 99713 ; [9,1,95,17,5] resulta en 9955171 . No estoy seguro de una respuesta.

sorted(x, cmp=lambda a, b: -1 if str(b)+str(a) < str(a)+str(b) else 1)

Intuitivamente, podemos ver que un tipo inverso de números de un solo dígito podría llevar al número más alto:

 >>> ''.join(sorted(['1', '5', '2', '9'], reverse=True)) '9521' 

así que la clasificación inversa debería funcionar. El problema surge cuando hay fragmentos de varios dígitos en la entrada. Aquí, la intuición nos permite nuevamente ordenar 9 antes de 95 y 17 antes de 1 , pero ¿por qué funciona eso? Nuevamente, si hubieran tenido la misma longitud, habría sido claro cómo clasificarlos:

 95 < 99 96 < 97 14 < 17 

El truco entonces, es 'extender' números más cortos para que puedan compararse con los más largos y se puedan clasificar de manera automática, lexicográficamente. Todo lo que necesita hacer, en realidad, es repetir el fragmento de código más allá de la longitud máxima:

  • comparando 9 y 95 : compara 999 y 9595 lugar y, por lo tanto, 999 es lo primero.
  • comparando 1 y 17 : compara 111 y 1717 lugar y, por lo tanto, 1717 es lo primero.
  • comparando 132 y 13 : compara 132132 y 1313 lugar y por lo tanto 132132 es lo primero.
  • comparando 23 y 2341 : compara 232323 y 23412341 en 23412341 lugar y por lo tanto 2341 viene primero.

Esto funciona porque Python solo necesita comparar los dos fragmentos hasta que difieran en algún lugar; y es (repitiendo) los prefijos coincidentes que debemos omitir cuando comparamos dos fragmentos de código para determinar en qué orden deben estar para formar un número mayor.

Solo necesita repetir un fragmento de código hasta que sea más largo que el fragmento de código más largo * 2 en la entrada para garantizar que puede encontrar el primer dígito no coincidente al comparar dos fragmentos de código.

Puede hacer esto con un argumento key para sorted() , pero primero debe determinar la longitud máxima de los fragmentos. Usando esa longitud, puedes "rellenar" todos los fragmentos en la clave de clasificación hasta que sean más largas que la longitud máxima:

 def largestpossible(snippets): snippets = [str(s) for s in snippets] mlen = max(len(s) for s in snippets) * 2 # double the length of the longest snippet return ''.join(sorted(snippets, reverse=True, key=lambda s: s*(mlen//len(s)+1))) 

donde s*(mlen//len(s)+1) rellena el fragmento para que mlen longitud superior a la de mlen .

Esto da:

 >>> combos = { ... '12012011': [1201, 120, 1], ... '87887': [87, 878], ... '99713': [97, 9, 13], ... '9955171': [9, 1, 95, 17, 5], ... '99799713': [97, 9, 13, 979], ... '10100': [100, 10], ... '13213': [13, 132], ... '8788717': [87, 17, 878], ... '93621221': [936, 21, 212], ... '11101110': [1, 1101, 110], ... } >>> def test(f): ... for k,v in combos.items(): ... print '{} -> {} ({})'.format(v, f(v), 'correct' if f(v) == k else 'incorrect, should be {}'.format(k)) ... >>> test(largestpossible) [97, 9, 13] -> 99713 (correct) [1, 1101, 110] -> 11101110 (correct) [936, 21, 212] -> 93621221 (correct) [13, 132] -> 13213 (correct) [97, 9, 13, 979] -> 99799713 (correct) [87, 878] -> 87887 (correct) [1201, 120, 1] -> 12012011 (correct) [100, 10] -> 10100 (correct) [9, 1, 95, 17, 5] -> 9955171 (correct) [87, 17, 878] -> 8788717 (correct) 

Tenga en cuenta que esta solución es a) 3 líneas cortas yb) funciona también en Python 3 sin tener que recurrir a functools.cmp_to_key() yc) no refuerza la solución (que es lo que hace la opción itertools.permutations ).

Una pista: concatena cadenas, no enteros. Sugerencia dos: itertools.permutations() .

 import itertools nums = ["9", "97", "13"] m = max(("".join(p) for p in itertools.permutations(nums)), key = int) 

Puede usar itertools.permutations como se sugiere y usar el argumento clave de la función max (que le dice qué función aplicar a cada elemento para decidir el máximo) después de que los cumpla con la función join.

Para empezar, es más fácil trabajar con cuerdas.

No me gusta el enfoque de fuerza bruta para esto. Requiere una gran cantidad de cómputo para grandes conjuntos.

Puede escribir su propia función de comparación para el método incorporado ordenado , que devolverá un parámetro de clasificación para cualquier par, según la lógica que ponga en la función.

Código de muestra:

 def compareInts(a,b): # create string representations sa = str(a) sb = str(b) # compare character by character, left to right # up to first inequality # if you hit the end of one str before the other, # and all is equal up til then, continue to next step for i in xrange(min(len(sa), len(sb))): if sa[i] > sb[i]: return 1 elif sa[i] < sb[i]: return -1 # if we got here, they are both identical up to the length of the shorter # one. # this means we need to compare the shorter number again to the # remainder of the longer # at this point we need to know which is shorter if len(sa) > len(sb): # sa is longer, so slice it return compareInts(sa[len(sb):], sb) elif len(sa) < len(sb): # sb is longer, slice it return compareInts(sa, sb[len(sa):]) else: # both are the same length, and therefore equal, return 0 return 0 def NumberFromList(numlist): return int(''.join('{}'.format(n) for n in numlist)) nums = [97, 9, 13, 979] sortednums = sorted(nums, cmp = compareInts, reverse = True) print nums # [97, 9, 13, 979] print sortednums # [9, 979, 97, 13] print NumberFromList(sortednums) # 99799713 

Bueno, siempre está el enfoque de fuerza bruta …

 from itertools import permutations lst = [9, 1, 95, 17, 5] max(int(''.join(str(x) for x in y)) for y in permutations(lst)) => 9955171 

O esto, una adaptación de la respuesta de @ Zah que recibe una lista de enteros y devuelve un entero, como se especifica en la pregunta:

 int(max((''.join(y) for y in permutations(str(x) for x in lst)), key=int)) => 9955171 

Puedes hacer esto con una ordenación inteligente.

Si dos cadenas tienen la misma longitud, elija la más grande de las dos que aparecerán primero. Fácil.

Si no tienen la misma longitud, calcule cuál sería el resultado si la mejor combinación posible se agregara a la más corta. Como todo lo que sigue al más corto debe ser igual o menor que él, puedes determinarlo añadiéndolo a sí mismo hasta que tenga el mismo tamaño que el más largo. Una vez que tienen la misma longitud, haces una comparación directa como antes.

Si la segunda comparación es igual, has probado que la cadena más corta no puede ser mejor que la más larga. Dependiendo de lo que esté emparejado, aún podría salir peor, por lo que cuanto más tiempo debe aparecer primero.

 def compare(s1, s2): if len(s1) == len(s2): return -1 if s1 > s2 else int(s2 > s1) s1x, s2x = s1, s2 m = max(len(s1), len(s2)) while len(s1x) < m: s1x = s1x + s1 s1x = s1x[:m] while len(s2x) < m: s2x = s2x + s2 s2x = s2x[:m] return -1 if s1x > s2x or (s1x == s2x and len(s1) > len(s2)) else 1 def solve_puzzle(seq): return ''.join(sorted([str(x) for x in seq], cmp=compare)) >>> solve_puzzle([9, 1, 95, 17, 5]) '9955171' >>> solve_puzzle([97, 9, 13]) '99713' >>> solve_puzzle([936, 21, 212]) '93621221' >>> solve_puzzle([87, 17, 878]) '8788717' >>> solve_puzzle([97, 9, 13, 979]) '99799713' 

Esto debería ser mucho más eficiente que ejecutar todas las permutaciones.

 import itertools def largestInt(a): b = list(itertools.permutations(a)) c = [] x = "" for i in xrange(len(b)): c.append(x.join(map(str, b[i]))) return max(c)