Построение наибольшего числа возможно путем перегруппировки списка

Ответ 1

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

Ответ 2

Интуитивно мы видим, что обратный вид чисел с одной цифрой приведет к наивысшему числу:

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

поэтому обратная сортировка должна работать. Проблема возникает, когда на входе есть многозначные фрагменты. Здесь интуиция снова позволяет нам заказывать 9 до 95 и 17 до 1, но почему это работает? Опять же, если бы они были одинаковой длины, было бы ясно, как их сортировать:

95 < 99
96 < 97
14 < 17

Тогда трюк состоит в том, чтобы "расширять" более короткие числа, чтобы их можно было сравнивать с более длинными и их можно сортировать автоматически, лексикографически. Все, что вам нужно сделать, это повторить фрагмент до максимальной длины:

• сравнение 9 и 95: сравните 999 и 9595, и, таким образом, 999 появится первым.
• сравнение 1 и 17: сравните 111 и 1717, и, таким образом, 1717 появится первым.
• сравнение 132 и 13: сравните 132132 и 1313, и, таким образом, 132132 появится первым.
• сравнение 23 и 2341: сравните 232323 и 23412341 и, таким образом, 2341 появится первым.

Это работает, потому что python нужно сравнить только два фрагмента, пока они не будут отличаться; и он (повторяя) сопоставимые префиксы, которые нам нужно пропустить при сравнении двух фрагментов, чтобы определить, в каком порядке они должны быть, чтобы сформировать наибольшее число.

Вам нужно только повторить фрагмент, пока он не станет длиннее самого длинного фрагмента * 2 на входе, чтобы гарантировать, что вы можете найти первую несогласованную цифру при сравнении двух фрагментов.

Вы можете сделать это с аргументом key до sorted(), но сначала вам нужно определить максимальную длину фрагментов. Используя эту длину, вы можете "набивать" все фрагменты в ключе сортировки до тех пор, пока они не будут длиннее этой максимальной длины:

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)))

где s*(mlen//len(s)+1) заполняет фрагмент с длиной более mlen длиной.

Это дает:

>>> 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)

Обратите внимание, что это решение: a) 3 строки короткие и b) также работает на Python 3, не прибегая к functools.cmp_to_key() и c) не выполняет команду brutforce (что делает опция itertools.permutations).

Ответ 3

Подсказка: вы объединяете строки, а не целые числа. Подсказка: itertools.permutations().

Ответ 4

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

Вы можете использовать itertools.permutations в качестве намеченного и использовать ключевой аргумент функции max (которая сообщает, какая функция применяется к каждому элементу, чтобы решить максимум) после того, как вы соедините их с функцией объединения.

С самого начала проще работать со строками.

Ответ 5

Мне не нравится подход грубой силы к этому. Это требует большого количества вычислений для больших наборов.

Вы можете написать свою собственную функцию сравнения для sorted встроенного метода, который вернет параметр сортировки для любой пары на основе любого логику, которую вы ввели в функцию.

Пример кода:

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

Ответ 6

Ну, всегда есть подход грубой силы...

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

Или это, адаптация ответа @Zah, которая получает список целых чисел и возвращает целое число, как указано в вопросе:

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

Ответ 7

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

Если две строки имеют одинаковую длину, выберите более крупную из двух, чтобы она была первой. Легко.

Если они не имеют одинаковой длины, выясните, что было бы результатом, если бы лучшая комбинация была добавлена ​​к более короткой. Поскольку все, что следует за более коротким, должно быть равно или меньше, чем это, вы можете определить это, добавив короткий к себе, пока он не будет иметь тот же размер, что и более длинный. Как только они имеют одинаковую длину, вы делаете прямое сравнение по-прежнему.

Если второе сравнение равно, вы доказали, что более короткая строка не может быть лучше, чем более длинная. В зависимости от того, что он в паре с ним, все еще может ухудшиться, поэтому дольше нужно идти первым.

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'

Это должно быть гораздо более эффективным, чем выполнение всех перестановок.

Ответ 8

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)