【Python】足すとnになるすべての自然数の組み合わせを求める

「足すとnになる自然数の組み合わせ」ってみなさん考えたことありますか?

この記事を読まれる方なら理系の方が多いと思いますので、「足すとnになる自然数の組み合わせ」と日本語で書くより、

\displaystyle{\sum_{i}} w_i = n

をみたす、自然数w_iの組

と書いたほうがわかりやすいでしょうか?

足すとnになるすべての自然数の組み合わせ

たまたま、大学で考える機会があったので、その防備録、勉強になったことの記録として記事に残したいと思います。

まずはnに具体的な数字を代入して、みていきます。

例:足すと4になる自然数の組み合わせ(n=4)

\displaystyle{\sum_{i}} w_i = 4

を満たすような自然数の組み合わせを全部書き下すと、以下のようになります。

(1,1,1,1),(1,1,2),(1,3),(2,2),(4)

もちろん、組み合わせなので順序は考慮しません。また、自分自身(この場合は「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)」と関数定義の前に書くだけでメモ化ができるのでやらない手はない。

参考:https://docs.python.org/ja/3/library/functools.html

「PyQ」と「みんなのPython」をやっててよかった

今回の「足すとnになるすべての自然数の組み合わせを求める」コードを書くことで以下の3つのことがらが身についたと思います。

  • 関数の再起呼び出し
  • itertools
  • メモ化

Python,もといプログラミングを勉強し始めて1年も経っていないんですが、この辺の知識をなんとか組み合わせてコードを書けたのも、PyQ」や「みんなのPython」で勉強してたからだな~と思っています。

だって、知らない知識は使えないし、検索できないですよね?知識のインプットは大事だと改めて実感しました。

参考 PyQ:https://pyq.jp/

特にPyQは自分の手を動かして学ぶことができる、かつ、Pythonのことなら幅広く学べるので初心者にはオススメです。



スポンサードリンク








コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です