Python 足し算の組み合わせ

Question

入力された4つの数字を2つのグループに分け、2桁の整数とし足し算した場合の最大値を求める方法がわかりません。
例えば3 4 5 6 を入力した場合、和が最大となる組み合わせが64 + 53 = 117となるようにプログラムしたいです。for文やitertoolsも検討したのですが、12組の組み合わせを抽出できず、力技しか思いつきませんでした。

a,b,c,d = map(int, input().split())

combi = []
combi.append(int((a*10 + b) + (c * 10 + d)))
combi.append(int((a*10 + b) + (d * 10 + c)))
combi.append(int((a*10 + c) + (b * 10 + d)))
combi.append(int((a*10 + c) + (d * 10 + b)))
combi.append(int((a*10 + d) + (b * 10 + c)))
combi.append(int((a*10 + d) + (c * 10 + b)))
combi.append(int((b*10 + a) + (c * 10 + d)))
combi.append(int((b*10 + a) + (d * 10 + c)))
combi.append(int((b*10 + c) + (a * 10 + d)))
combi.append(int((b*10 + c) + (d * 10 + a)))
combi.append(int((b*10 + d) + (a * 10 + c)))
combi.append(int((b*10 + d) + (c * 10 + a)))

print(max(combi))

初歩的な質問で申し訳ありませんが、よろしくお願い致します。

Answer 1

こんにちは

与えられた４つの数を小さい順にソートして、a, b, c, d とします。a, b, c, d には同じ数も含むものと考えれば、以下が成り立ちます。

a ≦ b ≦ c ≦ d

a と組にする数は、b, c, d の3とおりあります。a が最小ですので、和が最大値となり得るのは、a を1の位にするときです。同じように、aを含む2数以外の2数についても、和が最大値となり得るのは、小さいほうの数を1の位にしたときなので、以下の３つの数のどれかが最大値になることが分かります。

α = (10b + a) + (10d + c)
β = (10c + a) + (10d + b)
γ = (10d + a) + (10c + b)

このうち、αとβを比較してみます。

β - α = (10c + a) + (10d + b) - {(10b + a) + (10d + c)}
　　　 = 10c + a + 10d + b - 10b - a - 10d - c
　　　　= 9c - 9b
　　　　= 9(c - b) ≧ 0 （∵ c ≧ b )

よって、β ≧ α　であることがわかり、最大値は βかγになるので、βからγを引いてみます。

β - γ = (10c + a) + (10d + b) - {(10d + a) + (10c + b)}
    　=  10c + a + 10d + b - 10d - a - 10c - b
      = 0

となって、β = γ であることが分かります。

なので、α、β、γの大小関係は、α ≦ β = γ となって、

β = (10c + a) + (10d + b)

または

γ = (10d + a) + (10c + b)

のいずれで合計を作っても、それらは等しく、題意の最大値となります。

以下は、上記を試すコードです。

• 動作確認用 Repl.it: https://repl.it/@jun68ykt/Q268845

乱数から a, b, c, d を作り、2数の組み合わせのリストを x に作り、そこから題意の2桁の数の和のリスト(上記の説明のα、β、γに相当)を作って、最大値を得るコードです。
以上、参考になれば幸いです。

追記

上記のような検討をせずに、たとえばリスト [1, 2, 3, 4] から 12 + 34 を求めることにして、すべての組み合わせから、2桁の2数の和を求めて最大値を出すのは、以下でできます。

from itertools import permutations

max([(e1 + e3)*10 + (e2 + e4) for e1, e2, e3, e4 in permutations([a, b, c, d])])

ただし、順列（permutations）を使っていますし、調べる中には、10の位の数が1の位の数よりも小さい組み合わせも含むので、だいぶ無駄が多いです。（こちらのコードも上記のRepl.itに含めておきました）

Comments

[Justin04]

ありがとうございます！問題のとおりに組み合わせ試さなければいけないと考えてましたが、まず最大の組み合わせを見つければよいのですね。

Answer 2

lst = list(map(int, input().split()))
# 6 4 5 3 と入力
lst.sort()
a = lst[-1] * 10 + lst[-3] # 64
b = lst[-2] * 10 + lst[-4] # 53
print(a + b)
# 117
```ソートすると [3, 4, 5, 6] になって
64 + 53 か 63 + 54 が一番大きいので
こうなります。

Comments

[Justin04]

回答ありがとうございます！litの中の[]がマイナスになっているのはどういった理由でしょうか？
list[0]とかだと問題ありますか？

[ForestSeo]

問題ありません。
マイナスは、最後から数えるので大きい順になってると思ってください。
lst[-1]が一番大きい数字で、-2 -3 の順で小さくなってるという感じです。

[Justin04]

丁寧な回答ありがとうございます。無事解決できました。

Answer 3

答え書いてしまって申し訳ないですが、この問題であればitertools使う必要はないと思います。

a,b,c,d = reversed(sorted(map(int, input().split())))

print((a*10 + c) + (b*10 + d))

入力を逆順(じゃなくてもいいです)にソートして大きい数を10の位に見たてて計算している感じになります。

Comments

[Justin04]

ありがとうございます！全ての組み合わせを試さなければいけないと思いこんでいました…。ありがとうございます。