記事の内容
初歩的なプログラムの知識だけで解ける数学パズルの問題を紹介します。
プログラミング入門者の方にとっては、数学パズルはアルゴリズム的思考の訓練になります。楽しみながら慣れていきましょう。
プログラム入門者の方、python入門者のかたにおすすめの記事です。
今回扱うテーマは、「組み合わせの再帰生成」です。
それでは、目次をご覧ください。
問い 両替する方法を数える
「問題解決のPythonプログラミング 数学パズルで鍛えるアルゴリズム的思考」という本に載っている問題です。問題と解法をまとめさせてもらいます。
所持している紙幣の種類によって、目的の金額をはらう方法はいくつあるか？
たとえば、1ドル、2ドル、5ドル紙幣を持っている際に、6ドルという金額は紙幣のどんな組み合わせで払うことができるか？
[1, 5]、[1,1,2,2]、[2,2,2]などの組み合わせが考えられる。
こうした組み合わせの問題は、所持している紙幣の種類、目標金額が大きくなれば、とても大きくなってしまうことが予想できる。人が数えるにはめんどくさすぎる。すべての組み合わせを求めることのできるプログラムを書いてみよう。
方針
まずは、目標金額に達するまで紙幣を追加していけばよさそう。それには、今所持している紙幣のリストから1枚選ぶ。それを繰り返していく。再帰で実装するのがよさそう。目標金額に達したとき、目標金額を超えたときをのぞき、再帰でくりかえす。
Python実装
def makeChange(bills, target, sol = [] ): if sum(sol) == target: print(sol) return if sum(sol) > target: return for bill in bills: newSol = sol[:] #コピーして新しい用のリストを作らないと、要素が削除されない。 newSol.append(bill) makeChange(bills, target, newSol) return
実行結果を見ましょう。
所持している紙幣のリストは、[1, 2, 5]のとき。目標金額は6ドルです。
bills = [1, 2, 5] makeChange(bills, 6) >>> [1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 2] [1, 1, 1, 2, 1] [1, 1, 2, 1, 1] [1, 1, 2, 2] [1, 2, 1, 1, 1] [1, 2, 1, 2] [1, 2, 2, 1] [1, 5] [2, 1, 1, 1, 1] [2, 1, 1, 2] [2, 1, 2, 1] [2, 2, 1, 1] [2, 2, 2] [5, 1]
重複を削除したい
得られたリストをみると、重複しているものがあります。重複なしのリストを得るにはどうすればいいでしょうか。
[1,1,1,2,1]
[5,1]
ではなく、
[1,1,1,1,2]
[1,5]
にしたい。要素の大きさに注目して、整列させてやればよさそうです。整列といえばソートアルゴリズムです。得られたリストをそれぞれすべて整列させる。しかし、これでは遠回りのような気がします。
そこで、リストに要素を再帰的に追加する際に、今使っている最大紙幣以上の紙幣だけを追加させます。そうすれば、自然と整列したリストだけが生成されます。重複したものはそもそも生成すらされません。
先ほどの関数の引数に、最大紙幣を表すための引数highestを追加します。
実装
def makeChange(bills, target, highest, sol = [] ): if sum(sol) == target: print(sol) return if sum(sol) > target: return for bill in bills: if bill >= highest: #新しい種類の紙幣が、現在使用している最大紙幣以上のときだけ追加。 newSol = sol[:] #コピーして新しい用のリストを作らないと、要素が削除されない。 newSol.append(bill) makeChange(bills, target, bill, newSol) return
結果
bills = [1, 2, 5] #追加したhighest分の引数に注意 makeChange(bills, 6, 1) >>> [1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 2] [1, 1, 2, 2] [1, 5] [2, 2, 2]
ばっちり改良できましたね。
さらに思考錯誤
今回の数学パズルでは、組み合わせを再帰的に生成することがキモになります。pythonのいろいろなモジュールでは、「組み合わせ」を簡単に作ってくれるものがあるはずです。それを使うことで、よりpythonらしいコードにできるはずです。
次のコードの組み合わせを使います。
#combinations、組み合わせ、順列 from itertools import permutations, combinations,combinations_with_replacement,product a=['a','b','C'] print(list(permutations(a))) print(list(combinations(a,2))) print(list(combinations_with_replacement(a,3)))
結果
>>> [('a', 'b', 'C'), ('a', 'C', 'b'), ('b', 'a', 'C'), ('b', 'C', 'a'), ('C', 'a', 'b'), ('C', 'b', 'a')] [('a', 'b'), ('a', 'C'), ('b', 'C')] [('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'a', 'C'), ('a', 'b', 'b'), ('a', 'b', 'C'), ('a', 'C', 'C'), ('b', 'b', 'b'), ('b', 'b', 'C'), ('b', 'C', 'C'), ('C', 'C', 'C')]
この組み合わせの方法を今回利用してみると、次のようになりました。
shihei = [1,2,5] for i in [2,3,4,5,6]: kai = list(combinations_with_replacement(shihei,i)) for t in kai: if sum(t) == 6: print(t)
このコードの結果は、重複なしverと同じになります。とても簡単に書けました。
より詳しくは、本書へと進んでみてください。他にも面白い数学パズルを楽しめます。
