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

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.

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

For example, given [50, 2, 1, 9], the largest formed number is 95021.

例如,给定[50,2,1,9],最大形成数为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))

However, I get 50921 , as 50 is largest, but it should show 9 first.

但是,我得到50921,因为50是最大的,但它应该首先显示9。

7 个解决方案

#1

In Python 2 you can do this with an appropriate comparison function passed to sort.

在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://*.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

output

In:  [50, 2, 1, 9]
Out: [9, 50, 2, 1]

In:  [10, 1]
Out: [1, 10]

In:  [2, 23, 21]
Out: [23, 2, 21]

---

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".

在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://*.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('')

output

In:  [50, 2, 1, 9]
Out: [9, 50, 2, 1]

In:  [10, 1]
Out: [1, 10]

In:  [2, 23, 21]
Out: [23, 2, 21]

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.

我发布的以前的Python 3兼容版本实际上并不适用于Python 3:oops:!那是因为Python 3中不再支持__cmp__方法。因此我将旧的__cmp__方法更改为_cmp并使用它来实现所有6种丰富的比较方法。

Important note

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.

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

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.

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

---

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.

正如Antti Haapala在评论中指出的那样,当比较由重复数字的相同序列组成的不同数字时,我的旧比较函数是不稳定的,例如123123和123123123.这些序列应该相等,我的旧函数没有这样做。最新的修改解决了这个问题。

---

Update

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.

事实证明,mycmp()/ _cmp()实际上是可传递的。它也很稳定,因为它正确处理了ab == ba的情况,所以使用TimSort(或任何其他排序算法)是安全的。并且可以证明它与Antti Haapala的fractionalize()键函数具有相同的结果。

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.

在下面我将使用大写字母表示列表中的整数,我将使用字母的小写版本来表示该整数中的位数。例如,a是A中的位数。我将使用_作为中缀运算符来表示数字连接。例如,A_B是int(str(A)+ str(B);注意A_B有+ b个数字。算术上,A_B = A * 10 ** b + B.

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).

为简洁起见,我将使用f()来表示Antti Haapala的fractionalize()键函数。注意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.

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. :)

数学归纳式参数表明,使用成对比较mycmp()/ _cmp()作为比较函数或使用fractionalize()作为键函数排序任何有限长度的列表足以找到产生最大可能整数的置换由数字串联产生。这个论点的细节将留给读者练习。 :)

#2

One-liner using insights from Antti Haapala, PM 2Ring and Stefan Pochmann:

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)

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

给定a = [50,5,51,59,2,1,9,88]:

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

#3

Here is an ugly solution that does work without passing a cmp comparison function to the sorted. Basically, the key function takes each number and calculates a rational number that has that number as the repeating decimals; that is

这是一个丑陋的解决方案,可以在不将cmp比较函数传递给已排序的情况下工作。基本上,关键函数接受每个数字并计算一个有理数,该数字具有该数字作为重复小数;那是

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

The 0 is sorted the smallest with sort key 0, and 1 followed by most zeroes would have key closest to 0.1, and thus sorted second smallest. Numbers that consist of digit 9 all have sort key equal to 1; it does not really matter if you sort 9 before or after 99.

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

Sorting using these values as the key will necessarily give the correct output, unless you use numbers that are too big for float precision. (probably much sooner than 2 ** 53)

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

Thus we get the following program:

因此我们得到以下程序:

# 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))

Which produces

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

---

As we're essentially calculating i / (10 ** ceil(log10(i + 1)) - 1) here, one can also write the following oneliner:

由于我们基本上在这里计算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))

The i and part guards for division by zero error, in case 0 is among the numbers.

除了0之外,i和部分保护除以零错误,在0的情况下是数字。

#4

I hope I'm not varying too much on this. My input is cast as a list of strings. I generate the list of permutations, creating a list of lists, and then sort the sublists from least to greatest. Finally, I take the last element of the sorted list.

我希望我在这方面的变化不大。我的输入被转换为字符串列表。我生成排列列表,创建列表列表,然后将子列表从最小到最大排序。最后,我采用排序列表的最后一个元素。

import itertools

digits = ['50', '2', '1', '9']
perms = itertools.permutations(digits)
sorted_numlist = sorted(perms)
print sorted_numlist[-1]

If you'd rather have the number itself rather than the list of elements...

如果您更愿意拥有数字本身而不是元​​素列表......

import itertools

digits = ['11', '68', '4', '12']
perms = itertools.permutations(digits)
numlist = []
for sublist in perms:
    permutated_num = "".join(sublist)
    numlist.append(int(permutated_num))

sorted_numlist = sorted(numlist)
print sorted_numlist[-1]

That second one actually also serves to show the the first is properly sorting on lists.

第二个实际上也用于显示第一个正确排序列表。

I'm pretty new with Python and would appreciate comments/improvements.

我是Python的新手,非常感谢评论/改进。

#5

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))

#6

The most straight-forward way is to use itertools.permutations() to model how you would solve this by hand:

最直接的方法是使用itertools.permutations()来模拟如何手动解决这个问题:

>>> from itertools import permutations, imap
>>> a = [50, 2, 1, 9]
>>> int(max(imap(''.join, permutations(map(str, a)))))
95021

#7

I would love to understand from all the python experts here what is wrong with my one-liner solution. Leet code website keeps rejecting with failed tcs which works just fine on my local env.

我很想从这里的所有python专家那里了解我的单线解决方案有什么问题。 Leet代码网站一直拒绝使用失败的tcs,这在我的本地环境中运行得很好。

from itertools import permutations as pm

def max_number(lst):

    if all(v == 0 for v in nums):
        return "0"

    lst1 = [str(item) for item in lst]
    return max([int(''.join(list(perm))) for perm in pm(lst, len(lst1))])