21

正の整数の配列があるとします。結果の配列の連結が可能な最大数になるように順序を操作したいと思います。たとえば、次のよう[97, 9, 13]になります99713。[9,1,95,17,5]になります9955171。答えがわかりません。

4

8 に答える 8

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 に答える
9

直感的に、1 桁の数字を逆順に並べ替えると、最大の数字になることがわかります。

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

したがって、逆ソートが機能するはずです。入力に複数桁のスニペットがある場合に問題が発生します。ここでも、直観により9before95と17beforeを順序付けることができます1が、なぜそれが機能するのでしょうか? 繰り返しますが、それらが同じ長さであった場合、それらを並べ替える方法は明らかでした。

95 < 99
96 < 97
14 < 17

秘訣は、短い数値を「拡張」して、長い数値と比較し、辞書式に自動的にソートできるようにすることです。実際に行う必要があるのは、スニペットを最大長を超えて繰り返すことだけです。

  • 9comparison and 95:代わりに and を比較し、したがって最初999に来る。9595999
  • 1comparison and 17:代わりに and を比較し、したがって最初111に来る。17171717
  • 132comparison and 13:代わりに and を比較し、したがって最初132132に来る。1313132132
  • 23comparison and 2341:代わりに and を比較し、したがって最初232323に来る。234123412341

これが機能するのは、Python が 2 つのスニペットをどこかで異なるまで比較する必要があるためです。また、2 つのスニペットを比較して最大数を形成するためにどの順序にする必要があるかを判断するときにスキップする必要があるのは、(繰り返し) 一致するプレフィックスです。

2 つのスニペットを比較するときに一致しない最初の数字を確実に見つけることができるようにするには、入力内の最長のスニペット * 2 よりも長くなるまでスニペットを繰り返す必要があります。

keyへの引数を使用してこれを行うことができますがsorted()、最初にスニペットの最大長を決定する必要があります。その長さを使用すると、その最大長よりも長くなるまで、ソート キー内のすべてのスニペットを「パディング」できます。

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

スニペットをそれ自体でパディングして、長さs*(mlen//len(s)+1)以上mlenにします。

これは与える：

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

このソリューションは、a) 3 行短く、b) Python 3 でも頼りにせずに動作しfunctools.cmp_to_key()、c) ソリューションをブルートフォースしません (これがitertools.permutationsオプションの機能です)。

于 2013-01-26T18:10:03.123 に答える
5

ヒント 1: 整数ではなく、文字列を連結します。ヒント 2: itertools.permutations().

于 2013-01-25T23:46:36.050 に答える
3 
import itertools
nums =  ["9", "97", "13"]
m = max(("".join(p) for p in itertools.permutations(nums)), key = int)

itertools.permutationsをヒントとして使用し、結合関数と連結した後、max関数のkey引数（最大値を決定するために各要素に適用する関数を指示する）を使用できます。

そもそも文字列を扱う方が簡単です。

于 2013-01-26T00:23:37.153 に答える
2

私はこれに対する力ずくのアプローチが好きではありません。大規模なセットには大量の計算が必要です。

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
于 2013-01-26T01:18:37.190 に答える
1

ええと、ブルートフォースアプローチは常にあります...

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
于 2013-01-26T00:31:05.540 に答える
1

あなたはいくつかの巧妙な分類でこれを行うことができます。

2つの弦が同じ長さの場合は、2つのうち大きい方を最初に選択します。簡単。

それらが同じ長さでない場合は、可能な限り最良の組み合わせを短い方の組み合わせに追加した場合の結果を把握してください。短いものに続くものはすべてそれ以下でなければならないので、長いものと同じサイズになるまで短いものをそれ自体に追加することによってこれを決定できます。それらが同じ長さになったら、前と同じように直接比較します。

2番目の比較が等しい場合、短い文字列が長い文字列よりも優れている可能性はないことが証明されています。ペアリングされているものによっては、さらに悪化する可能性があるため、長い方が先に来る必要があります。

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'

これは、すべての順列を実行するよりもはるかに効率的です。

于 2013-01-26T02:27:14.757 に答える
0 
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)
于 2016-08-13T16:14:31.060 に答える