Pythonでリスト内の全要素を並べ替えて1つの文字列に結合するプログラム

問題の概要

正の整数からなるリストが与えられます。このリストを降順に並べ替えたうえで、すべての要素を連結して1つの文字列を作成し、その結果を返すことが求められます。

たとえば、入力が [415, 78, 954, 123, 5] の場合、出力は 954785415123 となります。ここで注意したいのは、単純に数値の大小で並べ替えるだけでは不十分なケースがあるという点です。「隣り合う要素を連結したときに最も大きな値になる」ように順序を決める必要があります。

解決のための手順

この問題は、以下の手順で解くことができます。

• 比較用の関数 cmp() を定義します。引数として l と r を受け取ります。
  • (l の文字列表現 + r の文字列表現) を整数化した値が、(r の文字列表現 + l の文字列表現) を整数化した値より大きい場合は 1 を返します。
  • それ以外の場合は -1 を返します。
• functools モジュールの cmp_to_key() を使って、この比較関数に基づいてリスト input をソートします。
• リスト input のすべての要素を文字列に変換して連結し、結果を返します。

比較関数が機能する仕組み

ポイントは、2つの数値 l と r の前後関係を「str(l) + str(r)」と「str(r) + str(l)」のどちらが大きいかで判定する点です。これにより、連結したときに最大の値になる順序が自動的に決まります。なお、Python 3 では sort() や sorted() に比較関数を直接渡すことができないため、cmp_to_key() でラップしてキー関数に変換する必要があります。

実装例

理解を深めるために、以下の実装例を見てみましょう。

from functools import cmp_to_key
def cmp(l, r):
    if int(str(l) + str(r)) > int(str(r) + str(l)):
        return 1
    else:
        return -1

def solve(input):
    input.sort(key=cmp_to_key(cmp), reverse=True)
    return "".join(map(str, input))

print(solve([415, 78, 954, 123, 5]))

入力

[415, 78, 954, 123, 5]

出力

954785415123