通过重新排列列表构建尽可能多的数字

Question

假设我有一组正整数; 我想操纵顺序,以便结果数组的串联是可能的最大数字.例如[97, 9, 13]结果99713; [9,1,95,17,5]结果9955171.我不确定答案.

Answer 1

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

Answer 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)不会强制解决方案(这是itertools.permutations选项的作用).

Answer 3

提示一:你连接字符串,而不是整数.提示二:itertools.permutations().