プロジェクトオイラー Problem15

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典： Project Euler （日本語翻訳サイト）
参考： サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 15
2 × 2 のマス目の左上からスタートした場合、
引き返しなしで右下にいくルートは 6 つある。

では、20 × 20 のマス目ではいくつのルートがあるか。

私の解答例は以下のとおりです。
－－－－－

def fact(n):
	if n<=0: return 1
	return fact(n-1)*n
	
def comb(n, m): return fact(n)//fact(n-m)//fact(m)

def f(a, b): return comb(a+b, a)

print f(20, 20)

－－－－－

引き返しなしなので、マス目の辺を合計(a+b)本分、通ることになります。
これより多いことも少ないこともありません。
つまり、この問題は縦線a本と横線b本を並べた、
縦、横、横、縦、・・・、縦
などという(a+b)個の配列のパターン数を求めること同じです。

また縦線以外は横線だけなので、どちらか一方の配置が決まれば、残りは全部もう一方という1パターンに決まります。
つまり、この問題は縦線a本を(a+b)個の置き場に散らした、
縦、○、○、縦、・・・、縦
などという(a+b)個の配列のパターン数と同じです。

さらには、先ほどの縦という文字の配置位置番号を取り出すと、
1,4,・・・,(a+b)
などという数列のパターン数と同じことです。
これは、(a+b)個の中からa個を選ぶ組合せのパターン数と同じです。

このように問題文を読み替えたところで、使用している関数の説明です。
ここでは３つの関数を使っています。
１．fact(n)
・nの階乗を返す関数です。
　階乗は記号!で表記し、1からnまでの積です。n! = 1x2x・・・xn です。
・if n<=0: return 1
 return fact(n-1)*n
「fact(n-1)*n」は、n-1の階乗値とnの積、つまりnの階乗を計算します。
このように、関数内で関数自分自身を呼び出す記述を「再帰」といいます。
if文は、nが0の場合に再帰を終了させるための設定です。
この記述があるのでn-1（1つ前）の階乗値を次々に求めていき、
nが0になったところまで遡って1が返り、
return文で戻りながら次々に積を計算していきます。

２．comb(n, m)
・組合せ(combination)の場合の数、aＣb を返す関数です。
・n個の中からm個を選ぶ選び方について、
　選ぶ順番を入れ替えたら違う組とする選び方を「順列」(permutation)といいます。
　選ぶ順番を入れ替えても同じ組とする選び方を「組合せ」(combination)といいます。
例）sとtという2つから2つ選ぶ場合
順列は(s,t)と(t,s)の2通り、組み合わせは(s,t)[または(t,s)]の1通りです。

n個の中からm個を選ぶ選び方が何通りあるかというパターン数、 数学用語では「場合の数」の公式は以下の通りです。
順列   nＰm = n!/(n-m)!
組合せ nＣm = n!/(n-m)!m!
（参考）順列(wikipedia)、組合せ(wikipedia)

2つの式の違いは分母の「m!」で、これは選んだものの内部で選んだ順番を入れ替えると同じになるパターン数です。
同時に選ぶなど、選んだものの中で順番を関係無し、入れ替えても同じで1パターンと見なすのが「組合せ」です。

例）5つのモノから2つ選ぶ場合
順列   5Ｐ2 = (5x4x3x2x1)/(3x2x1)= 5x4 = 20(通り)
組合せ 5Ｃ2 = (5x4x3x2x1)/{(3x2x1)x(2x1)} = (5x4)/(2x1) = 10(通り)

・fact(n)//fact(n-m)//fact(m)
 演算子//は整数部分までの割り算の商です。組合せnＣmを公式そのままの記述です。

３．f(a, b)
・縦a横bのマス目で左上から右下に引き返しなしでいくルート数です。
・comb(a+b, a)
(a+b)個の中からa個を選ぶ組合せのパターン数、(a+b)Ｃaを求めます。
縦線に注目するか横線に注目するかの違いなので、(a+b)Ｃbでも同じ答えです。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
137846528820
（追記）
・20120715
　関数fact()の停止条件をn==0 -> n<=0　に修正。
　nが0未満の場合、無限ループになるため。
・20120715
　ソースコード部分にSyntaxHighlighterを導入。