通过重排列表构造可能的最大数字

Question

假设我有一个正整数的数组，我想调整这些数字的顺序，使得把它们连在一起后能形成最大的数字。比如说，数组 [97, 9, 13] 组合起来会得到 99713; 而数组 [9,1,95,17,5] 组合后会得到 9955171。我还不太确定怎么做。

Answer 1

提示一：你是把字符串拼接在一起，而不是整数。
提示二：可以使用 itertools.permutations()。

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 只需要比较两个数字，直到它们的某个地方不同；而我们在比较两个数字时需要跳过的就是（重复的）匹配前缀，这样才能确定它们的顺序，以形成最大的数字。

你只需要重复一个数字，直到它的长度超过输入中最长数字的两倍，这样就能保证在比较两个数字时找到第一个不匹配的数字。

你可以通过给 sorted() 函数传递一个 key 参数来实现这个，但你需要先确定数字的最大长度。利用这个长度，你可以“填充”所有数字，使它们的长度超过这个最大长度：

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) 只有三行代码，b) 在 Python 3 中也能工作，不需要使用 functools.cmp_to_key()，c) 也没有使用暴力破解的方法（而 itertools.permutations 选项就是这样做的）。

Answer 3

这段代码的意思是对一个叫做 `x` 的东西进行排序。这里用到了一个比较函数，简单来说就是告诉程序怎么比较两个东西。这个比较函数的逻辑是：如果把 `b` 和 `a` 连接起来的结果比把 `a` 和 `b` 连接起来的结果小，就返回 -1；否则就返回 1。这样做的目的是为了让排序的结果按照特定的顺序排列。