Pythonで数値リストから作れる最大の数を求める2つの方法

この記事では、与えられた数値のリストを並べ替えて作れる「最大の数」を求める方法を解説します。例えば [45, 35, 138, 43, 67] というリストがあった場合、これらの数字をどのような順序で並べれば最も大きな整数になるのでしょうか。本記事では、全順列を試すシンプルな方法と、ソートを活用した効率的な方法の2つのアプローチを、コード例とともにわかりやすく紹介します。

方法1: itertools.permutationsで全順列を調べる

まずは、itertoolsモジュールのpermutationsメソッドを使って、考えられるすべての並び順(順列)を生成し、その中から最大値を探す方法です。以下の手順で実装します。

• itertoolsモジュールからpermutationsメソッドをインポートする
• 数値のリストと、結果を格納する空のリストを用意する
• リストの全順列をループで処理する
• 各順列の要素を連結した文字列を結果リストに追加する
• maxメソッドにkey=intを指定して最大値を求める
• 文字列を整数に変換して出力する

サンプルコード

# モジュールをインポート
import itertools

# リストを初期化
numbers = [45, 35, 138, 43, 67]

# 結果格納用のリスト
result = []

# 全順列を生成して連結
for permutation in itertools.permutations(str(number) for number in numbers):
    result.append(''.join(permutation))

# 最大値を取得
maximum = max(result, key=int)

# 最大値を出力
print(int(maximum))

実行結果

67454335138

このコードを実行すると、上記のように「67454335138」が出力されます。

方法2: sorted関数と比較関数を使った効率的な方法

次に、sorted関数とカスタム比較関数を組み合わせた、より効率的な方法を紹介します。手順は以下の通りです。

• リストをsorted関数に渡す
• 2つの引数を受け取るget_key関数を定義する
• str(first) + str(second) > str(second) + str(first) の場合は -1、そうでなければ 1 を返す
• joinメソッドでソート済みの要素を連結する
• 整数に変換して出力する

比較関数をkeyとして使う場合は、functoolsモジュールのcmp_to_keyメソッドでラップする必要がある点に注意してください。それではコードを見てみましょう。

サンプルコード

from functools import cmp_to_key

# リストを初期化
numbers = [45, 35, 138, 43, 67]

def get_key(first, second):
    if str(first) + str(second) > str(second) + str(first):
        return -1
    return 1

# ソートして結果を取得
result = sorted(numbers, key=cmp_to_key(get_key))

# 要素を連結
result = "".join(str(integer) for integer in result)

# 結果を出力
print(int(result))

実行結果

67454335138

2つの方法のパフォーマンス比較

両者の大きな違いは計算量です。方法1の順列生成はO(n!)となり、要素数が増えると処理時間が爆発的に伸びてしまいます。一方、方法2のソートベースのアプローチはO(n log n)で済むため、実用的な規模のデータでは圧倒的に高速です。実際の開発では、方法2を採用するのがおすすめです。

まとめ

この記事では、Pythonで数値リストから作れる最大の数を求める2つの方法を学びました。シンプルに全順列を試す方法と、比較関数によるソートで効率的に解く方法、どちらも理解しておくと役立つ場面が多いでしょう。このチュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。