python - 通过重新排列列表构建可能的最大数字

Question

假设我有一个正整数数组；我想操纵顺序，以便结果数组的串联是可能的最大数字。例如[97, 9, 13]结果99713；[9,1,95,17,5]结果9955171。我不确定答案。

score 12 · Accepted Answer

12

sorted(x, cmp=lambda a, b: -1 if str(b)+str(a) < str(a)+str(b) else 1)

于 2013-01-26T04:39:58.187 回答

score 9 · Accepted Answer

Intuitively, we can see that a reverse sort of single digit numbers would lead to the higest number:

>>> ''.join(sorted(['1', '5', '2', '9'], reverse=True))
'9521'

so reverse sorting should work. The problem arises when there are multi-digit snippets in the input. Here, intuition again lets us order 9 before 95 and 17 before 1, but why does that work? Again, if they had been the same length, it would have been clear how to sort them:

95 < 99
96 < 97
14 < 17

The trick then, is to 'extend' shorter numbers so they can be compared with the longer ones and can be sorted automatically, lexicographically. All you need to do, really, is to repeat the snippet to beyond the maximum length:

comparing 9 and 95: compare 999 and 9595 instead and thus 999 comes first.
comparing 1 and 17: compare 111 and 1717 instead and thus 1717 comes first.
comparing 132 and 13: compare 132132 and 1313 instead and thus 132132 comes first.
comparing 23 and 2341: compare 232323 and 23412341 instead and thus 2341 comes first.

This works because python only needs to compare the two snippets until they differ somewhere; and it's (repeating) matching prefixes that we need to skip when comparing two snippets to determine which order they need to be in to form a largest number.

You only need to repeat a snippet until it is longer than the longest snippet * 2 in the input to guarantee that you can find the first non-matching digit when comparing two snippets.

You can do this with a key argument to sorted(), but you need to determine the maximum length of the snippets first. Using that length, you can 'pad' all snippets in the sort key until they are longer than that maximum length:

def largestpossible(snippets):
    snippets = [str(s) for s in snippets]
    mlen = max(len(s) for s in snippets) * 2  # double the length of the longest snippet
    return ''.join(sorted(snippets, reverse=True, key=lambda s: s*(mlen//len(s)+1)))

where s*(mlen//len(s)+1) pads the snippet with itself to be more than mlen in length.

This gives:

>>> combos = {
...     '12012011': [1201, 120, 1],
...     '87887': [87, 878],
...     '99713': [97, 9, 13],
...     '9955171': [9, 1, 95, 17, 5],
...     '99799713': [97, 9, 13, 979],
...     '10100': [100, 10],
...     '13213': [13, 132],
...     '8788717': [87, 17, 878],
...     '93621221': [936, 21, 212],
...     '11101110': [1, 1101, 110],
... }
>>> def test(f):
...     for k,v in combos.items():
...         print '{} -> {} ({})'.format(v, f(v), 'correct' if f(v) == k else 'incorrect, should be {}'.format(k))
... 
>>> test(largestpossible)
[97, 9, 13] -> 99713 (correct)
[1, 1101, 110] -> 11101110 (correct)
[936, 21, 212] -> 93621221 (correct)
[13, 132] -> 13213 (correct)
[97, 9, 13, 979] -> 99799713 (correct)
[87, 878] -> 87887 (correct)
[1201, 120, 1] -> 12012011 (correct)
[100, 10] -> 10100 (correct)
[9, 1, 95, 17, 5] -> 9955171 (correct)
[87, 17, 878] -> 8788717 (correct)

Note that this solution is a) 3 lines short and b) works on Python 3 as well without having to resort to functools.cmp_to_key() and c) does not bruteforce the solution (which is what the itertools.permutations option does).

score 5 · Accepted Answer

5

提示一：你连接字符串，而不是整数。提示二：itertools.permutations()。

于 2013-01-25T23:46:36.050 回答

score 3 · Accepted Answer

import itertools
nums =  ["9", "97", "13"]
m = max(("".join(p) for p in itertools.permutations(nums)), key = int)

您可以按照提示使用 itertools.permutations 并在将它们与 join 函数连接后使用 max 函数的 key 参数（它告诉将哪个函数应用于每个元素以确定最大值）。

从一开始就使用字符串更容易。

score 2 · Accepted Answer

我不喜欢这种蛮力方法。对于大型集合，它需要大量的计算。

您可以为sorted内置方法编写自己的比较函数，该函数将根据您放入函数中的任何逻辑返回任何对的排序参数。

示例代码：

def compareInts(a,b):
    # create string representations
    sa = str(a)
    sb = str(b)

    # compare character by character, left to right
    # up to first inequality
    # if you hit the end of one str before the other, 
    # and all is equal up til then, continue to next step
    for i in xrange(min(len(sa), len(sb))):
        if sa[i] > sb[i]:
            return 1
        elif sa[i] < sb[i]:
            return -1

    # if we got here, they are both identical up to the length of the shorter
    # one.
    # this means we need to compare the shorter number again to the 
    # remainder of the longer
    # at this point we need to know which is shorter
    if len(sa) > len(sb): # sa is longer, so slice it
        return compareInts(sa[len(sb):], sb)
    elif len(sa) < len(sb): # sb is longer, slice it
        return compareInts(sa, sb[len(sa):])
    else:
        # both are the same length, and therefore equal, return 0
        return 0



def NumberFromList(numlist):
    return int(''.join('{}'.format(n) for n in numlist))

nums = [97, 9, 13, 979]
sortednums = sorted(nums, cmp = compareInts, reverse = True)
print nums # [97, 9, 13, 979]
print sortednums # [9, 979, 97, 13]
print NumberFromList(sortednums) # 99799713

score 1 · Accepted Answer

您可以通过一些巧妙的排序来做到这一点。

如果两个字符串的长度相同，请选择两个字符串中较大的一个。简单的。

如果它们的长度不同，请弄清楚如果将最佳组合附加到较短的组合会产生什么结果。由于较短的后面的所有内容都必须等于或小于它，因此您可以通过将短的附加到自身来确定这一点，直到它与较长的大小相同。一旦它们的长度相同，您就可以像以前一样进行直接比较。

如果第二个比较相等，则您已经证明较短的字符串不可能比较长的字符串更好。取决于它与之配对的内容可能会变得更糟，所以应该先出现更长的那个。

def compare(s1, s2):
    if len(s1) == len(s2):
        return -1 if s1 > s2 else int(s2 > s1)
    s1x, s2x = s1, s2
    m = max(len(s1), len(s2))
    while len(s1x) < m:
        s1x = s1x + s1
    s1x = s1x[:m]
    while len(s2x) < m:
        s2x = s2x + s2
    s2x = s2x[:m]
    return -1 if s1x > s2x or (s1x == s2x and len(s1) > len(s2)) else 1

def solve_puzzle(seq):
    return ''.join(sorted([str(x) for x in seq], cmp=compare))

>>> solve_puzzle([9, 1, 95, 17, 5])
'9955171'
>>> solve_puzzle([97, 9, 13])
'99713'
>>> solve_puzzle([936, 21, 212])
'93621221'
>>> solve_puzzle([87, 17, 878])
'8788717'
>>> solve_puzzle([97, 9, 13, 979])
'99799713'

这应该比遍历所有排列更有效。

score 1 · Accepted Answer

好吧，总是有蛮力的方法......

from itertools import permutations
lst = [9, 1, 95, 17, 5]

max(int(''.join(str(x) for x in y)) for y in permutations(lst))
=> 9955171

或者这个，@Zah 的答案的改编，它接收整数列表并返回一个整数，如问题中所指定：

int(max((''.join(y) for y in permutations(str(x) for x in lst)), key=int))
=> 9955171

score 0 · Accepted Answer

import itertools
def largestInt(a):
    b = list(itertools.permutations(a))
    c = []
    x = ""
    for i in xrange(len(b)):
        c.append(x.join(map(str, b[i])))
    return max(c)

python - 通过重新排列列表构建可能的最大数字

8 回答 8

Related

Reference