アルゴリズムと数学の問題を今日も解いています。
008 - Brute Force 1の問題でGithubにPythonの解答が見つからなかったのでうんうん唸りながら解きました。
問題文
赤・青のカードが各 1 枚ずつあり、あなたはそれぞれのカードに 1 以上 N 以下の整数を 1 つ書き込みます。
カードに書かれた整数の合計が S 以下となる書き方は、いくつありますか？
これは全探索と呼ばれるアルゴリズムのようで、productを使って以下のように書き上げることができました。
from itertools import product
N,S = list(map(int, input().split()))
l1 = range(1, N+1)
l = []
p = product(l1, l1)
for v in p:
sum = v[0]+v[1]
if sum <= S:
l.append(sum)
print(len(l))
何かもたついているような気もしますがどう変えたらいいのかわかりません。
ここでproductの基本的な使い方について記録を残しておこうと思います。
公式ドキュメントによると
ジェネレータ式の入れ子になった for ループとおよそ等価です。たとえば product(A, B) は ((x,y) for x in A for y in B) と同じものを返します。
だそうです。
入れ子のforは以下のようになるので
l1 = ['Tokyo', 'NY', 'Beijing']
l2 = [1, 2, 3]
for i in l1:
for j in l2:
print(i, j)
出力結果
Tokyo 1
Tokyo 2
Tokyo 3
NY 1
NY 2
NY 3
Beijing 1
Beijing 2
Beijing 3
これをタプルに入れてリストにすると
print(list((i, j) for i in l1 for j in l2))
print(produce(l1, l2))
この二つが同じ結果になるということですね。
出力結果
[('Tokyo', 1), ('Tokyo', 2), ('Tokyo', 3), ('NY', 1), ('NY', 2), ('NY', 3), ('Beijing', 1), ('Beijing', 2), ('Beijing', 3)]
ここから先はお遊び。
同数のカードの組み合わせを見るようなイメージです。
l1 = ['春', '夏', '秋']
l2 = ['さくら', 'ひまわり', 'こすもす']
print(list(product(l1, l2)))
>>[('春', 'さくら'), ('春', 'ひまわり'), ('春', 'こすもす'), ('夏', 'さくら'), ('夏', 'ひまわり'), ('夏', 'こすもす'), ('秋', 'さくら'), ('秋', 'ひまわり'), ('秋', 'こすもす')]
スイーツのある日曜日。どの組み合わせにしようかな。
l1 = ['コーヒー', 'カフェラテ', 'ココア']
l2 = ['クッキー', 'チップス', 'チョコ']
print(list(product(l1, l2)))
>>[('コーヒー', 'クッキー'), ('コーヒー', 'チップス'), ('コーヒー', 'チョコ'), ('カフェラテ', 'クッキー'), ('カフェラテ', 'チップス'), ('カフェラテ', 'チョコ'), ('ココア', 'クッキー'), ('ココア', 'チップス'), ('ココア', 'チョコ')]
ケーキ屋さんで2種類選べるとしたら、repeat=2を使って全ての組み合わせを列挙できる。
l3 = ['ティラミス', 'モンブラン', 'ショートケーキ']
print(list(product(l3, repeat=2)))
>> [('ティラミス', 'ティラミス'), ('ティラミス', 'モンブラン'), ('ティラミス', 'ショートケーキ'), ('モンブラン', 'ティラミス'), ('モンブラン', 'モンブラン'), ('モンブラン', 'ショートケーキ'), ('ショートケーキ', 'ティラミス'), ('ショートケーキ', 'モンブラン'), ('ショートケーキ', 'ショートケーキ')]
もう少し数学と絡めた方が勉強になりそうだけど、今日はここまで...