在Python 2中,您可以使用适当的比较函数传递给"sort"来实现此操作。
''' 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 https://dev59.com/UV0a5IYBdhLWcg3wmZsX
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
将比较函数转换为键函数,但是手动实现也不难。
''' 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 https://dev59.com/UV0a5IYBdhLWcg3wmZsX
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个
丰富比较方法。
重要提示
另一种保证可行的策略是暴力破解:生成输入列表的所有排列,并找到产生最大结果的排列。但希望有一种更有效的算法,因为生成大型列表的所有排列相当缓慢。
正如安蒂·哈帕拉在评论中指出的那样,我的旧比较函数在比较由相同重复数字序列组成的不同数字时是不稳定的,例如123123和123123123。这些序列应该被视为相等,但我的旧函数无法做到这一点。最新的修改解决了这个问题。
更新
事实证明,mycmp() / _cmp()
实际上是可传递的。现在它也是稳定的,因为它正确处理了 ab == ba
的情况,所以可以安全地与TimSort(或任何其他排序算法)一起使用。而且可以证明它给出的结果与 Antti Haapala 的 fractionalize()
关键字函数相同。
接下来,我将使用大写字母表示列表中的整数,并使用字母的小写版本表示该整数的位数。例如,a
是 A
中数字的数量。我将使用 _
作为中缀运算符表示数字连接。例如,A_B
是 int(str(A)+str(B)
;请注意,A_B
具有 a+b
位数字。从算术上讲,A_B = A * 10**b + B
。
为了简洁起见,我将使用
f()
来代表Antti Haapala的
fractionalize()
关键函数。请注意,
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()
作为键函数进行成对比较,可以对任何有限长度的列表进行排序,从而找到产生数字连接最大可能整数的排列。具体细节将留给读者作为练习。 :)
[2, 23, 21]
和[1, 10]
。 - Peter Mortensen