「足すとnになる自然数の組み合わせ」ってみなさん考えたことありますか？
この記事を読まれる方なら理系の方が多いと思いますので、「足すとnになる自然数の組み合わせ」と日本語で書くより、
をみたす、自然数w_iの組
と書いたほうがわかりやすいでしょうか？
足すとnになるすべての自然数の組み合わせ
まずはnに具体的な数字を代入して、みていきます。
例：足すと4になる自然数の組み合わせ(n=4)
を満たすような自然数の組み合わせを全部書き下すと、以下のようになります。
(1,1,1,1),(1,1,2),(1,3),(2,2),(4)
もちろん、組み合わせなので順序は考慮しません。また、自分自身（この場合は「４」という数字）ももちろん含めます。
人の手で書き出していくのは大変
nが1桁のうちは、まだなんとか人間の手で計算できなくもないですが、2桁を超えてくるとさすがに数え落としなどが起こりそうだし、そもそも大変。
（そもそも、n=8くらいから結構面倒では？）
たぶん、こういう計算はコンピュータの方が得意だろう！ということでPythonのコードを書きました。
Pythonでコードを書いてみた
プログラミングは勉強し始めてまだ1年も経っていないペーペーなりに頑張って書いてみました。
で、このコード書くだけでも勉強になることが結構ありました。
from functools import lru_cache import itertools @lru_cache(maxsize=None) def combination_of_number_totalN(N): if N == 1: return {(1,)} else: combination_set_totalN = {(N,)} middle_number = N // 2 for i in range(1, middle_number + 1): A, B = i, N - i combination_set_totalA = combination_of_number_totalN(A) combination_set_totalB = combination_of_number_totalN(B) for combination_totalA, combination_totalB in itertools.product(combination_set_totalA,combination_set_totalB): combination_total_N = combination_totalA + combination_totalB sorted_combination_totalN = sorted(combination_totalN) combination_set_totalN.add(tuple(sorted_combination_N)) return combination_set_totalN 足すとnになる自然数の組み合わせは、combination_of_number_totalN(n)の関数を呼び出すことで求められます。
あ、もしもっと効率の良い書き方や修正点などあったら教えてもらえると嬉しいです。
プログラムの方針
どのようにプログラムを作ろうか、考えた過程を下の図に書いてみます。
いきなりnとして考えるのは難しいので、足すと5になる自然数の組み合わせはどうやったら求められるかを考えます。
図にならって、足すとnになるすべての自然数の組み合わせの集合をset(n)と呼ぶことにしますが、set(5)は自分自身(「5」)以外の組み合わせは
- set(1)とset(4)の各要素を合体（ドッキング)させる
- set(2)とset(3)の各要素を合体（ドッキング)させる
ことで得られることがわかります。つまり、set(1)~set(4)が分かればよい。
一般の場合に拡張
set(n)は
- set(1)とset(n-1)の各要素を合体
- set(2)とset(n-2)の各要素を合体
- …
させて求めることができる。なんだか漸化式チックな感じで求まるんですね。
set(n)を求めるには、set(1)~set(n-1)の情報が必要なのです。
この考えをもとにプログラムを作っていきました。
関数の再起呼び出し
漸化式チックな処理をする、となったらやっぱり関数の再起呼び出しですよね。
関数の再起呼び出しとは、「ある関数の中でその関数自身を呼び出す」ことをいいます。
僕が今回作ったコードでも、combination_of_number_totalN(N)という関数のブロックの中でcombination_of_number_totalN(A)とその関数自身を呼び出していますよね。
関数の再起呼び出しは、簡単な例ですと、フィボナッチ数列を作るプログラムなんかによく使われていますよね。
def fib(n): if n < 2 : return n else: return fib(n-2) + fib(n-1)このコードはn番目のフィボナッチ数列の要素を返す関数。
同じく、fib(n)という関数の中でその関数自身を、fib(n-2),fib(n-1)といったように再起的に呼び出しています。
「フィボナッチ数列のn番目の項はn-1番目とn-2番目の項を足したものになっている」ことをわかっていれば、コードの理解は容易です。
itertoolsが便利
このコードを書く1〜2周間前くらいにちょうどitertoolsというライブラリの存在を知ったのですが、こんなすぐお世話になるときが来るとは。
本コードでは、集合の直積をとる場面でitertools.productを使っていますね。
念のため、直積を簡単に説明しておきます。
A={1,2},B={3,4,5}といった集合を考えたとき、AとBの直積は、
{(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)}という集合になります。
日本語で書くと、「集合A、集合Bから1つずつ要素を選んだときの考えうる、すべての組み合わせの集合」ですね。
直積を得たいとき、itertoolsを使わなければ
ABset = set() for a in A: for b in B: ABset.add((a,b))といったようにfor分を2重にネストして書く必要があります。しかし、itertoolsを使うと、
ABset = set(itertools.product(A,B)) だけで求まっちゃうんですね、しゅごい！
今回はたまたまitertoolsの中のproductという関数のみの紹介となりましたが、itertoolsには他にもいろんな強力な関数があるので、ぜひこれからも恩恵をあやかりたいところ。
参考：https://docs.python.org/ja/3/library/itertools.html
メモ化でより高速に計算（@lru_cache)
メモ化はたぶん関数の再起呼び出しと相性が良いみたい。
簡単のため、今回もフィボナッチ数列のコードを例に挙げますが…
フィボナッチ数列の8項目を先ほど紹介したフィボナッチ数列を求めるコードを使って求めるとしましょう。
fib(8)はfib(7)+fib(6)を計算する必要があるので、まずfib(7)とfib(6)を求める必要がありそうですね。
同様にfib(7)を求めるにはfib(6)とfib(5)が、fib(6)を求めるにはfib(5)とfib(4)の値が必要になります。
で、よく見てみると、同じ引数がよく登場しますよね。
たとえば、fib(5)とかfib(4)とか何回も登場していますが、でてくる毎にバカ真面目に計算すると効率わるくないですか？
fib(5)が最初に出てきたときは、まじめに計算するけど、2回目以降出てきたときは最初にfib(5)を計算した結果を覚えておいてそれを使う、というのがメモ化の考え方。
実際にこれをすることで、計算がかなり早くなります。
「@lru_cache(maxsize=None)」と関数定義の前に書くだけでメモ化ができるのでやらない手はない。
コメント