記事の内容
今回の記事では、基礎的な知識だけで解ける数学パズルを紹介します。
プログラミング、python初心者にとってはいい練習になるはずです。それに、アルゴリズムで問題を解くということのいい実践になります。
専門的には、最大独立集合問題と呼ばれるようです。目的の関係にあった組み合わせを求めるための考え方になります。
興味がある人は、ぜひ読んでいってください。
問題解決のPythonプログラミング 招かれざる客
「問題解決のPythonプログラミング 数学パズルで鍛えるアルゴリズム的思考」という本に載っている問題です。問題と解法をまとめさせてもらいます。
パーティーをするために、友人たちを招きたいと考えています。しかし、その友人たちの中には、互いを嫌っている場合があるのです。Alice、Bob、Eve、 Cleo、Donの5人を招待したいのですが、AliceとBob、BobとEveが互いに嫌いあっています。この「嫌い関係」を招かないように、少しでも多くの人を招待するにはどの組み合わせがいいでしょうか？それを解くプログラムを作りましょう。
今回の問題であれば、人数が少ないので、Bobを招かなければ、Alice、Eve、 Cleo、Donの4人を招待できることがわかります。ここに、「嫌い関係」はありませんよね。
しかし、コンピュータは莫大な数のものを対象とします。効率よく解けるプログラムを考えてみましょう。
方針
しらみつぶしに検索する。
・まずは、客のあらゆる組み合わせを全て列挙する
・「嫌い関係」を含む組み合わせを省く
・残った組み合わせの中で最大のものを答えとする
この方針ならば、どんな場合でも対応できそうです。
すべての組み合わせを生成する
文字列集合から、全ての組み合わせを求める方法はたくさんあります。n個の文字の組み合わせならば、組み合わせの数は2のn乗個にになる。
今回は、2進数に対応させることを考える。
[] なら 00000
[A,B] なら 11000
[B,C,D] なら 01110
このように列を2進数で表す。
def Combinations(n, guestList): allCombL = [] for i in range(2**n): num = i cList = [] for j in range(n): if num % 2 == 1: cList = [guestList[n - 1 - j ]] + cList num = num//2 allCombL.append(cList) return allCombL
「嫌い関係」を取り除き、最大のものを選ぶ
後のステップは、全ての組み合わせの中から、「嫌い関係」を取り除くこと。
def removeBadCombinations(allCombL, dislikePairs): allGoodCombinations = [] for i in allCombL: good = True for j in dislikePairs: if j[0] in i and j[1] in i : good = False if good: allGoodCombinations.append(i) return allGoodCombinations
そして、最大の組み合わせを選ぶ。
def InviteDinner(guestList, dislikePairs): allCombL = Combinations(len(guestList), guestList) allGoodCombinations = removeBadCombinations(allCombL, dislikePairs) #リストならmax使った方が楽 ''' invite = [] for i in allGoodCombinations: if len(i) > len(invite): invite = i ''' invite = max(allGoodCombinations, key = len) print('Optimum Solution:', invite)
さらに効率よく解けないか？
このコードでは、2のn乗個の要素のリストを作ることになる。つまり、大量のメモリを消費してしまう。
リストに格納する前に、その組み合わせが適当かどうかをチェックしてしまえばいい。適当な組み合わせのみを格納する。
def InviteDinnerOptimized(guestList, dislikePairs): n, invite = len(guestList), [] for i in range(2**n): Combination = [] num = i for j in range(n): if (num % 2 == 1): Combination = [guestList[n - 1- j]] + Combination num = num // 2 good = True for j in dislikePairs: if j[0] in Combination and j[1] in Combination: good = False if good: if len(Combination) > len(invite): invite = Combination print('Optimum Solution:', invite)
より詳しくは、本書へと進んでみてほしい。他にも面白い数学パズルを楽しめる。
