对列表进行排序以形成最大可能的数字

Question

我正在尝试编写一个给出非负整数列表的函数,将它们排列成最大可能的数字.

例如,给定[50, 2, 1, 9],最大的数字是95021.

这是我试图解决问题的代码:

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第一.

Answer 1

在Python 2中,您可以使用传递给的适当比较函数来完成此操作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将比较函数转换为关键函数,但"手工"并不难.

#!/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:!那是因为__cmp__Python 3不再支持该方法.所以我将旧__cmp__方法改为_cmp并使用它来实现所有6种丰富的比较方法.

重要的提示

我必须提到这个比较函数有点奇怪:它是不可传递的,换句话说,a> b和b> c并不一定意味着a> c.这意味着使用它的结果.sort()是不可预测的.它似乎对我测试过的数据做了正确的事情,例如,它为所有排列返回正确的结果[1, 5, 10],但我想对所有输入都应该不值得信任.

保证工作的另一种策略是强力:生成输入列表的所有排列并找到产生最大结果的排列.但希望有一种更有效的算法,因为生成大型列表的所有排列都相当慢.

正如Antti Haapala在评论中指出的那样,当比较由重复数字的相同序列组成的不同数字时,我的旧比较函数是不稳定的,例如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()作为关键函数对任何有限长度的列表进行排序足以找到产生由数字级联产生的最大可能整数的置换.这个论点的细节将留给读者练习.:)

Answer 2

One-liner使用Antti Haapala,PM 2Ring和Stefan Pochmann的见解:

from fractions import Fraction
sorted(a, key=lambda n: Fraction(n, 10**len(str(n))-1), reverse=True)

鉴于a = [50, 5, 51, 59, 2, 1, 9, 98]:

[9, 98, 59, 5, 51, 50, 2, 1]

Answer 3

这是一个丑陋的解决方案,无需将cmp比较功能传递给sorted.基本上,关键函数接受每个数字并计算一个有理数,该数字具有该数字作为重复小数 ; 那是

0   => 0
100 => 100/999 == 0.100100100...
10  => 10/99   == 0.1010101010...
1   => 1/9     == 0.1111111111...
11  => 11/99   == 0.1111111111...
12  => 12/99   == 0.1212121212...
9   => 9/9     == 1
99  => 99/99   == 1
999 => 999/999 == 1

使用排序键0将0排序为最小值,并且1后跟大多数零将具有最接近的键0.1,因此排序第二小.由数字9组成的数字都具有等于的排序键1; 如果你9在之前或之后排序并不重要99.

使用这些值作为键进行排序必然会提供正确的输出,除非您使用的数字对于浮点精度而言太大.(可能早得多2 ** 53)

因此我们得到以下程序:

# for Python 2, not needed in Python 3
from __future__ import division

a = [50, 5, 51, 59, 2, 1, 9, 98]

def fractionalize(i):
    divisor = 9
    while divisor < i:
        divisor = 10 * divisor + 9 

    return i / divisor

print(sorted(a, key=fractionalize, reverse=True))

哪个产生

[9, 98, 59, 5, 51, 50, 2, 1]

正如我们在i / (10 ** ceil(log10(i + 1)) - 1)这里计算的那样,人们也可以编写以下oneliner:

from math import ceil, log10

print(sorted(a, key=lambda i: i and i/(10**ceil(log10(i+1))-1), reverse=True))

该i and部分警卫除以零差错,万一0是数量当中.

Answer 4

import functools

def cmpr(x, y):
    xy = str(x) + str(y)
    yx = str(y) + str(x)
    return -1 if (xy > yx) else 1

a = [50, 2, 1, 9]
a.sort(key=functools.cmp_to_key(cmpr))