形成lis中可能的最大数量

Question

给出如下清单： [3,30,34,5,9]。 输出：9534330 编写一个程序以返回尽可能大的数

在我的代码中，我在这里使用了置换：

from itertools import permutations
x = [3, 30, 34, 5, 9]
y = permutations(x)
n = len(y)
e = []
for i in y:
    a = map(str, i)
    e.append(int("".join(i)))
print "Largest Number {}".format(sorted(e)[-1])

这里n是置换数的长度，是120，因为5！。 有没有更好的方法来解决这个问题？在

Answer 1

这个问题的解决导致了一个有趣的转变，值得解释。在

假设我们想知道对于给定的X和{}，哪个{}或{}哪个更大。在数值上，我们需要X.10^y + Y和Y.10^x + X中的最大值，其中小写表示大写变量的位数。在

再加上一点数学比较

X.10^y + Y < Y.10^x + X

可以重写

^{pr2}$

因此XY < YX确实是一个传递关系，它定义了一个全序。这是一个非常好的消息，因为这意味着通过使用这种修改后的比较操作，问题可以简化为普通排序。在

现在请注意，X / (10^x - 1)是0.XXXX...形式的一个周期分数，要比较0.XXXX...和{}，只需在最长的周期内进行比较就足够了。因此，比较可以像普通的字符串比较一样工作，只是当到达较短字符串的结尾时，我们会循环回到第一个字符。在

例如，12345 > 12是因为12345 > 12|12|1，而{}是因为12105 < 12|12|1。在

比较功能描述如下：

def Cmp(X, Y):
    l= max(len(X), len(Y))
    for i in range(l):
        if X[i % len(X)] < Y[i % len(Y)]:
            return 1 # X > Y
        elif X[i % len(X)] > Y[i % len(Y)]:
            return -1 # X < Y
    return 0 # X == Y

我不推荐这种特定的实现，因为%，它会很慢。在

Answer 2

按降序排列所有数字是我们遇到的最简单的解决方案。但这行不通。在

例如，548大于60，但在输出中，60在548之前。作为第二个例子，98大于9，但是在输出中9在98之前。在

解决方案是使用任何基于比较的排序算法。因此，与其使用默认比较，不如编写一个比较函数myCompare（）并使用它对数字进行排序。在

给定两个数字X和Y，myCompare（）如何决定将哪个数字放在第一位–我们比较两个数字XY（Y附加在X末尾）和YX（X附加在Y末尾）。在

如果XY较大，那么在输出中，X应该在Y之前，否则Y应该在X之前

例如，让X和Y分别是542和60。为了比较X和Y，我们比较了54260和60542。因为60542大于54260，所以我们把Y放在第一位。在

计算排列会产生更高的时间复杂度。 python中更好的解决方案是：

def largestNumber(A):
    maxlen = len(str(max(A)))
    if all(v == 0 for v in A):
        return '0'
    return ''.join(sorted((str(v) for v in A), reverse=True,
                      key=lambda i: i*(maxlen * 2 // len(i))))

largestNumber([3, 30, 34, 5, 9])