对列表进行排序以形成可能的最大数字 [英] Sort a list to form the largest possible number
问题描述
我正在尝试编写一个函数，该函数给出一个非负整数列表，将它们排列成尽可能大的数字.
I am trying to write a function that given a list of non negative integers, arranges them such that they form the largest possible number.
例如，给定[50, 2, 1, 9]，最大的组成数是95021.
For example, given [50, 2, 1, 9], the largest formed number is 95021.
这是我尝试解决问题的代码:
Here is the code that I have tried to solve the problem:
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.
However, I get 50921 , as 50 is largest, but it should show 9 first.
推荐答案
在 Python 2 中，您可以使用传递给 sort 的适当比较函数来完成此操作.
In Python 2 you can do this with an appropriate comparison function passed to 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 将比较函数转换为关键函数，但手动"并不难.
In Python 3, sort no longer takes a custom comparison function. scpio's answer shows how to use functools to convert a comparison function into a key function, but it's not that hard to do "by hand".
#!/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 :oops:!那是因为 Python 3 不再支持 __cmp__ 方法.所以我将旧的 __cmp__ 方法更改为 _cmp 并用它来实现全部 6 个丰富的比较方法.
The previous Python 3 compatible version I posted doesn't actually work on Python 3 :oops:! That's because the __cmp__ method is no longer supported in Python 3. So I've changed my old __cmp__ method to _cmp and used it to implement all 6 of the rich comparison methods.
重要提示
我不得不提到这个比较函数有点奇怪:它是非传递的，换句话说，a>b 和 b>c 并不必然暗示 a>c.这意味着在 .sort() 中使用它的结果是不可预测的.它似乎对我测试过的数据做了正确的事情，例如，它为 [1, 5, 10] 的所有排列返回正确的结果，但我想它真的应该不信任对所有输入都这样做.
I have to mention that this comparison function is a bit weird: it's non-transitive, in other words, a>b and b>c doesn't necessarily imply a>c. And that means that the results of using it in .sort() are unpredictable. It does appear to do the right thing for the data I've tested it with, eg, it returns the correct result for all permutations of [1, 5, 10], but I guess it really shouldn't be trusted to do so for all input.
一种保证有效的替代策略是蛮力:生成输入列表的所有排列 &找到产生最大结果的排列.但希望有一个更有效的算法，因为生成一个大列表的所有排列相当慢.
An alternative strategy that's guaranteed to work is brute force: generate all permutations of the input list & find the permutation that yields the maximum result. But hopefully there's a more efficient algorithm, since generating all permutations of a large list is rather slow.
正如 Antti Haapala 在评论中指出的那样，我的旧比较函数在比较由相同重复数字序列组成的不同数字时不稳定，例如 123123 和 123123123.这样的序列应该比较相等，我的旧函数没有这样做那.最新的修改解决了这个问题.
As Antti Haapala points out in the comments, my old comparison functions were unstable when comparing different numbers that consist of the same sequences of repeating digits, eg 123123 and 123123123. Such sequences should compare equal, my old functions didn't do that. The latest modification addresses that problem.
更新
事实证明，mycmp()/_cmp() 实际上是可传递的.它也很稳定，现在它可以正确处理 ab == ba 情况，因此可以安全地与 TimSort(或任何其他排序算法)一起使用.并且可以证明它给出了与 Antti Haapala 的 fractionalize() 键函数相同的结果.
It turns out that mycmp() / _cmp() actually is transitive. It's also stable, now that it handles the ab == ba case properly, so it's safe to use with TimSort (or any other sorting algorithm). And it can be shown that it gives the same result as Antti Haapala's fractionalize() key function.
在接下来的内容中，我将使用大写字母表示列表中的整数，并使用小写字母表示该整数中的位数.例如，a 是A 中的位数.我将使用 _ 作为中缀运算符来表示数字连接.例如，A_B 是 int(str(A)+str(B)；注意 A_B 有 a+b> 数字.算术上，A_B = A * 10**b + B.
In what follows I'll use uppercase letters to represent integers in the list and I'll use the lowercase version of a letter to represent the number of digits in that integer. Eg, a is the number of digits in A. I'll use _ as an infix operator to represent digit concatenation. Eg, A_B is int(str(A)+str(B); note that A_B has a+b digits. Arithmetically,
A_B = A * 10**b + B.
为了简洁起见，我将使用 f() 来表示 Antti Haapala 的 fractionalize() 键函数.注意f(A) = A/(10**a - 1).
For the sake of brevity, I'll use f() to represent Antti Haapala's fractionalize() key function. Note that f(A) = A / (10**a - 1).
现在是一些代数.我会把它放在一个代码块中以保持格式简单.
Now for some algebra. I'll put it in a code block to keep the formatting simple.
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() 作为关键函数就足够了找到产生最大可能整数的排列由数字连接产生.这个论点的细节将是留给读者作为练习.:)
A mathematical induction-style argument shows that sorting a list of any
finite length using pairwise comparisons with mycmp() / _cmp() as the
comparison function or with fractionalize() as the key function suffices
to find the permutation that yields the largest possible integer
produced by digit concatenation. The details of this argument will be
left as an exercise for the reader. :)
这篇关于对列表进行排序以形成可能的最大数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
