Сортируйте список, чтобы сформировать максимально возможное число

Question

Я пытаюсь написать функцию, которая задала список не отрицательных целых чисел, упорядочивает их так, чтобы они составляли максимально возможное число.

Например, если [50, 2, 1, 9], то наибольшим образованным номером является 95021.

Вот код, который я попытался решить эту проблему:

a = [50, 2, 1, 9] 
a.sort() 
ans = [] 
for i in range(len(a)-1,-1,-1): 
    ans.append(a[i]) 

print ''.join(map(str,ans)) 

Однако я получаю 50921 как 50 является самым большим, но он должен показать 9 в первую очередь.

Answer 1

import functools 

def cmpr(x, y): 
    xy = str(x) + str(y) 
    yx = str(y) + str(x) 
    return -1 if (xy > yx) else 1 

a = [50, 2, 1, 9] 
a.sort(key=functools.cmp_to_key(cmpr)) 

Answer 2

В Python 2 вы можете сделать это с помощью соответствующей функции сравнения передается sort.

#!/usr/bin/env python 

''' Sort a list of non-negative integers so that 
    if the integers were converted to string, concatenated 
    and converted back to int, the resulting int is the highest 
    possible for that list 

    From http://stackoverflow.com/q/30140796/4014959 

    Written by PM 2Ring 2015.05.10 

    Python 2 version 
''' 

data = [ 
    [50, 2, 1, 9], 
    [10, 1], 
    [2, 23, 21], 
] 

def mycmp(a, b): 
    a, b = str(a), str(b) 
    ab, ba = a + b, b + a 
    if ab == ba: 
     return 0 
    if ab < ba: 
     return -1 
    return 1 

for a in data: 
    print 'In: ', a 
    a.sort(cmp=mycmp, reverse=True) 
    print 'Out:', a 
    print 

выход

In: [50, 2, 1, 9] 
Out: [9, 50, 2, 1] 

In: [10, 1] 
Out: [1, 10] 

In: [2, 23, 21] 
Out: [23, 2, 21] 

---

В Python 3 sort больше не принимает пользовательскую функцию сравнения. Ответ scpio показывает, как использовать functools для преобразования функции сравнения в ключевую функцию, но это не так сложно сделать «вручную».

#!/usr/bin/env python 

''' Sort a list of non-negative integers so that 
    if the integers were converted to string, concatenated 
    and converted back to int, the resulting int is the highest 
    possible for that list 

    From http://stackoverflow.com/q/30140796/4014959 

    Written by PM 2Ring 2015.05.10 

    Python 3 compatible version 
''' 

from __future__ import print_function 

class cmpclass(object): 
    def __init__(self, n): 
     self.n = str(n) 

    def __str__(self): 
     return self.n 

    def _cmp(self, other): 
     a, b = self.n, str(other) 
     ab, ba = a + b, b + a 
     if ab == ba: 
      return 0 
     if ab < ba: 
      return -1 
     return 1 

    def __lt__(self, other): return self._cmp(other) == -1 
    def __le__(self, other): return self._cmp(other) <= 0 
    def __eq__(self, other): return self._cmp(other) == 0 
    def __ne__(self, other): return self._cmp(other) != 0 
    def __gt__(self, other): return self._cmp(other) == 1 
    def __ge__(self, other): return self._cmp(other) >= 0 


data = [ 
    [50, 2, 1, 9], 
    [10, 1], 
    [2, 23, 21], 
] 

for a in data: 
    print('In: ', a) 
    a.sort(key=cmpclass, reverse=True) 
    print('Out:', a) 
    print('') 

выход

In: [50, 2, 1, 9] 
Out: [9, 50, 2, 1] 

In: [10, 1] 
Out: [1, 10] 

In: [2, 23, 21] 
Out: [23, 2, 21] 

Предыдущий Python 3 совместимая версия я разместил на самом деле не работает на Python 3: упс :! Это потому, что метод __cmp__ больше не поддерживается в Python 3. Поэтому я изменил свой старый метод __cmp__ на _cmp и использовал его для реализации всех 6 из rich comparison methods.

Важное примечание

Я должен отметить, что эта функция сравнения немного странно: это непереходный, другими словами, а> Ь и Ь> с не обязательно подразумевают > с. А это означает, что результаты его использования в .sort(): непредсказуемый. Кажется, он делает правильные вещи для данных, которые я тестировал, например, он возвращает правильный результат для всех перестановок [1, 5, 10], но я думаю, на самом деле не следует доверять этому для всех входных данных.

альтернативная стратегия, это гарантированно работать это перебор: генерировать все перестановки списка входных & найти перестановку, которая дает максимальный результат. Но, надеюсь, существует более эффективный алгоритм, поскольку генерация всех перестановок большого списка происходит довольно медленно.

---

Как Antti Haapala указывает в комментариях, мои старые функции сравнения были нестабильны при сравнении различных чисел, которые состоят из одних и тех же последовательностей повторяющихся цифр, например 123123 и 123123123. Такие последовательности должны сравнивать равные, мои старые функции не сделал этого.Последняя модификация затрагивает эту проблему.

---

Update

Оказывается, что на самом деле mycmp()/_cmp()является транзитивно. Он также стабилен, теперь он правильно обрабатывает корпус ab == ba, поэтому его можно использовать с TimSort (или любым другим алгоритмом сортировки). И можно показать, что он дает тот же результат, что и ключевая функция Антти Хаапалы fractionalize().

В дальнейшем я буду использовать прописные буквы для представления целых чисел в списке, и я буду использовать строчную версию буквы для представления числа цифр в этом целочисленном значении. Например, a - это количество цифр в A. Я буду использовать _ в качестве оператора инфикса для представления конкатенации цифр. Например, A_B - int(str(A)+str(B); обратите внимание, что A_B имеет a+b цифр. Арифметически,
A_B = A * 10**b + B.

Для краткости я буду использовать f() для представления функции ключа fractionalize() от Antti Haapala. Обратите внимание, что f(A) = A/(10**a - 1).

Теперь для некоторой алгебры. Я поставлю его в блок кода, чтобы упростить форматирование.

Let A_B = B_A 
A * 10**b + B = B * 10**a + A 
A * 10**b - A = B * 10**a - B 
A * (10**b - 1) = B * (10**a - 1) 
A/(10**a - 1) = B/(10**b - 1) 
f(A) = f(B) 

So A_B = B_A if & only if f(A) = f(B) 

Similarly, 
A_B > B_A if & only if f(A) > f(B) 
This proves that using mycmp()/_cmp() as the sort comparison function 
is equivalent to using fractionalize() as the sort key function. 

Note that 
f(A_B) = (A * 10**b + B)/(10**(a+b)-1) 
and 
f(B_A) = (B * 10**a + A)/(10**(a+b)-1) 

So f(A_B) = f(B_A) iff A_B = B_A, and f(A_B) > f(B_A) iff A_B > B_A 

Let's see what happens with 3 integers. 

f(A), f(B), f(C) are just real numbers, so comparing them is 
transitive. 
And so if f(A) > f(B) and f(B) > f(C) then f(A) > f(C). 
This proves that mycmp()/_cmp() is also transitive. 

Clearly, if f(A) > f(B) > f(C) then 
A_B > B_A, B_C > C_B, A_C > C_A 

Let B_C > C_B 
For any A, 
A * 10**(b+c) + B_C > A * 10**(b+c) + C_B 
So A_B_C > A_C_B 
i.e. adding the same integer to the beginning of B_C and C_B preserves 
the inequality. 

Let A_B > B_A 
For any C, 
(A_B) * 10**c + C > (B_A) * 10**c + C 
So A_B_C > B_A_C, 
i.e. adding the same integer to the end of A_B and B_A preserves the 
inequality. 

Using these results, we can show that 
if f(A) > f(B) > f(C) then 
A_B_C > A_C_B > C_A_B > C_B_A and 
A_B_C > B_A_C > B_C_A > C_B_A. 

This covers all 6 permutations of [A, B, C] and shows that A_B_C is the 
largest possible integer for that list. 

математического аргумент индукции стиль показывает, что сортировка списка любого конечной длины с использованием парных сравнений с mycmp()/_cmp() как функция сравнения или с fractionalize() в качестве функциональной клавиши достаточно найти перестановку, что доходность максимально возможное целое число , созданное путем конкатенации цифр. Подробности этого аргумента будут слева как упражнение для читателя. :)

Answer 3

Это уродливое решение, которое работает без передачи функции сравнения cmp на sorted. В принципе, ключевая функция принимает каждое число и вычисляет рациональное число, которое имеет это число как repeating decimals; что

0 => 0 
100 => 100/999 == 0.100100100... 
10 => 10/99 == 0.1010101010... 
1 => 1/9  == 0.1111111111... 
11 => 11/99 == 0.1111111111... 
12 => 12/99 == 0.1212121212... 
9 => 9/9  == 1 
99 => 99/99 == 1 
999 => 999/999 == 1 

0 сортируется наименьшее с рода ключом 0 и 1 с последующим большинство нулей будет иметь ключ ближе всего к 0.1, и, таким образом, отсортированный второй маленький. Числа, состоящие из цифры 9, имеют ключ сортировки, равный 1; это не имеет большого значения, если вы сортируете 9 до или после 99.

Сортировка с использованием этих значений в качестве ключа обязательно даст правильный результат, если вы не используете слишком большие числа для точности поплавка.(Вероятно, гораздо раньше, чем 2 ** 53)

Таким образом, мы получаем следующую программу:

# for Python 2, not needed in Python 3 
from __future__ import division 

a = [50, 5, 51, 59, 2, 1, 9, 98] 

def fractionalize(i): 
    divisor = 9 
    while divisor < i: 
     divisor = 10 * divisor + 9 

    return i/divisor 

print(sorted(a, key=fractionalize, reverse=True)) 

Который производит

[9, 98, 59, 5, 51, 50, 2, 1] 

---

Как мы по существу вычисления i/(10 ** ceil(log10(i + 1)) - 1) здесь, можно также написать нижеследующий oneliner:

from math import ceil, log10 

print(sorted(a, key=lambda i: i and i/(10**ceil(log10(i+1))-1), reverse=True)) 

Защитные элементы i and для деления на нулевую ошибку, в случае, если 0 относится к числу номеров.

Answer 4

Однострочник используя идеи из Антти Haapala, П.М. 2Ring и Стефан Pochmann:

from fractions import Fraction 
sorted(a, key=lambda n: Fraction(n, 10**len(str(n))-1), reverse=True) 

Учитывая a = [50, 5, 51, 59, 2, 1, 9, 98]:

[9, 98, 59, 5, 51, 50, 2, 1] 

Answer 5

Я надеюсь, что я не варьируя слишком много об этом. Мой ввод представлен как список строк. Я генерирую список перестановок, создавая список списков, а затем сортирует подсписок от наименьшего до наибольшего. Наконец, я беру последний элемент отсортированного списка.

import itertools 

digits = ['50', '2', '1', '9'] 
perms = itertools.permutations(digits) 
sorted_numlist = sorted(perms) 
print sorted_numlist[-1] 

Если вы хотели бы иметь сам номер, а не список элементов ...

import itertools 

digits = ['11', '68', '4', '12'] 
perms = itertools.permutations(digits) 
numlist = [] 
for sublist in perms: 
    permutated_num = "".join(sublist) 
    numlist.append(int(permutated_num)) 

sorted_numlist = sorted(numlist) 
print sorted_numlist[-1] 

Это второй один на самом деле также служит, чтобы показать первый правильно сортировать по спискам.

Я довольно новичок в Python и буду благодарен за комментарии/улучшения.

Answer 6

Самый прямой способ заключается в использовании itertools.permutations() модели, как вы бы решить эту проблему вручную:

>>> from itertools import permutations, imap 
>>> a = [50, 2, 1, 9] 
>>> int(max(imap(''.join, permutations(map(str, a))))) 
95021