Pythonで階乗の計算をする

Pythonで階乗の計算をします。数学の中ではそれ自体も面白いテーマですが、階乗の考え方は場合の数の順列や組み合わせにも応用することができます。SymPyモジュールなどには階乗に関して多くの関数が用意されていますが、自分で作ることができるようになると、応用範囲がより広がります。

Pythonで5の階乗5!を計算する

定義通りに階乗を計算する関数

基本来な考え方

変数numに対してnumの階乗num!を変数valで計算します。

  1. # 1 for文を使い自然数の階乗を計算する
  2. num = 5
  3. val = 1
  4. for i in range(num, 1, -1): # for i in range(2,num+1): でもOK
  5. val *= i
  6. print(val)

120

  1. 4行目では、num=5から変数iを1つずつ減らして5,4,3,2までループします。コメントしたようにrange(2,num+1)とすると2,3,4,5までループすることができますが、5!=5×4×3×2(×1)という定義に従いました。
  2. 3行目でvalを定義し、6行目で階乗計算するためvalを順次、掛け合わせていきます。掛け算の累積になるので初期値は1にします。

for文を使って階乗を求める関数にする

#1のプログラムを関数に書き換えます。引数に5を指定すると、5!=120を返します。

  1. # 2 for文を使い自然数の階乗を計算する関数
  2. def factorial_for(num):
  3. val = 1
  4. for i in range(num, 1, -1):
  5. val *= i
  6. return val
  7. factorial_for(5)

while文を使って階乗を求める関数

#2と同じ考え方でwhile文を使って階乗を計算します。

  1. # 3 while文を使い自然数の階乗を計算する関数
  2. def factorial_while(num):
  3. val = 1
  4. while num > 0: # while num: ,while num > 1:でもOK
  5. val *= num
  6. num -= 1
  7. return val
  8. factorial_while(5)

  1. whileループの中でnumを順次減らしながらvalに掛けていきます。
  2. whileループは numが0以上である限り繰り返し、0になったところで抜けて、戻り値として階乗を返します。
  3. 4行目でコメントした通りwhile num:とした場合、numが0になるとwhileを抜けるようになるので結果は同じです。
  4. 同様にwhile num > 1:としても5,4,3,2までの積になるので結果は同じです。

階乗を計算する関数をforループとwhileループと2つの方法で作成しました。次にどちらの方が、応用が利くか試してみます。

再帰関数を使って階乗を計算する

pythonをはじめ多くのプログラミング言語では再帰関数を使うことができます。うまく使うと複雑なプログラムを簡単に書くことができます。階乗のような単純な計算ではあえて再帰関数を使う必要はありませんが、練習のために作ってみます。

  1. #4 再帰関数を使い自然数の階乗を計算する
  2. def factorial_recursive(num):
  3. if num == 0:
  4. return 1
  5. else:
  6. return num * factorial_recursive(num-1)
  7. factorial_recursive(5)

モジュールの組み込み関数を使って階乗を計算する

mathモジュールsympyモジュールで階乗を計算する関数

階乗は数学的にもよく使われる計算なので、多くのモジュールで関数が用意されています。いずれも、factorial関数に求めたい階乗の自然数を指定するだけです。

  1. #5 mathモジュールを使い階乗を計算する
  2. import math
  3. print('math モジュールによる計算:',math.factorial(5))
  4. import sympy
  5. print('sympyモジュールによる計算:',sympy.factorial(5))

math モジュールによる計算: 120
sympyモジュールによる計算: 120

いずれも同じ結果になります。

NumPyモジュールで階乗の計算をする関数

関数による計算

NumPyモジュールでも階乗の計算をすることができます。NumPyモジュールでは、mathという特殊機能にfactorial関数が用意されているので、3行目のように,np.math.factorial(5))とする必要があります。

  1. #6 NumPyモジュールで階乗を計算する
  2. import numpy as np
  3. print('math.factorial関数の計算:',np.math.factorial(5))
  4. f=np.arange(1,6)
  5. print('np.arange(1,6)の配列の値:',f)
  6. print('prod関数で配列の積を計算:',np.prod(f))

math.factorial関数の計算: 120
np.arange(1,6)の配列の値: [1 2 3 4 5]
prod関数で配列の積を計算: 120

ちなみに、1~5まで、NumPyのndarrayで作成し、prod関数で、配列の積を求めても同じように計算できます。

リストの積を求める

NumPyにはリストの積を求める関数が用意されていますが、NumPyを使わない場合は#7のproduct関数を自作する必要があります。

もっとも、Numpyのprod関数はndarray形式だけでなく、Pythonの配列の積にも対応しています。

  1. # 7リストの各要素の積を計算する
  2. list = [5, 4, 3, 2, 1]
  3. def product(list):
  4. product = 1
  5. for i in list:
  6. product *= i
  7. return product
  8. print('リストの合計 :',sum(list))
  9. print('リストの積  :',product(list))
  10. print('リストも計算可:',np.prod(list))

リストの合計 : 15
リストの積  : 120
リストも計算可: 120

sympyモジュールで素数であるかを判定する関数
sympy.isprime(n)

引数で指定した値が素数であればTrue、そうでなければFalseを返す

sympyモジュールで関数
sympy.prime(n)

小さいものから数えてn番目の素数を返す

sympyモジュールで関数
sympy.primepi(7) (n)

引数で指定した数値より小さい素数の数を返す

sympyモジュールで関数
sympy.primerange(101, 200)

小さいものから数えてn番目の素数を返す

sympyモジュールで関数
sympy.nextprime(10,1)

小さいものから数えてn番目の素数を返す

ympy.randprime(100, 200)

小さいものから数えてn番目の素数を返す

Pythonで二重階乗、n乗階乗を計算する

二重階乗の計算

for文による計算

階乗の応用として二重階乗があり、数え上げ理論などで活躍します。二重階乗は次の定義のように、自然数nから2つ飛びに階乗を計算します。

$\displaystyle n!!=\left\{{n(n-2)\cdots3\cdot1\hspace{20px} n\gt0\ 偶数\ \atop n(n-2)\cdots4\cdot2\hspace{20px}n\gt0\ 奇数}\right.\ $

つまり、nが偶数の場合は2まで、nが奇数の場合は1(計算上は3でもOK)まで計算することになります。

定義通り計算すると次の通りになります。num=10,11で計算して検証すると正しい結果になっています。

  1. # 8 forループで二重階乗を計算する
  2. def factorial2_for(num):
  3. if num % 2 == 0:
  4. stop = 2
  5. else:
  6. stop = 1
  7. val = 1
  8. for i in range(num, stop-1, -2):
  9. val *= i
  10. return val
  11. print(10, 'even', 10*8*6*4*2, factorial2_for(10))
  12. print(11, 'odd ', 11*9*7*5*3*1, factorial2_for(11))

10 even 3840 3840
11 odd  10395 10395

  1. 定義通り、掛け算を止める値をstopとすると偶数の場合2、奇数の場合は1になります。奇数の場合は、1を掛けても結果は変わらないので3までとしても結果は同じです。
  2. for文はrange(num, stop-1, -2)とすることにより、数字が大きい方から下がってくるときにはstopまでループします。
  3. print文では、定義通り計算した結果と一致することがわかります。

while文による計算

  1. # 9 whileループで二重階乗を計算する
  2. def factorial2_while(num):
  3. val = 1
  4. while num > 0:
  5. val *= num
  6. num -= 2
  7. return val
  8. print(10, 'even', 10*8*6*4*2, factorial2_while(10))
  9. print(11, 'odd ', 11*9*7*5*3*1, factorial2_while(11))

10 even 3840 3840
11 odd  10395 10395

  1. whileを使うとnum>0として、num -= 2として2ずつかける数を減らしていくようにすると自然に偶数の場合には2、奇数の場合には1で計算が止まります。
  2. 4行目は奇数のときには3で計算を終えれば結果は同じなので、while num > 1としても問題ありません。
  3. print文では、定義通り計算した結果と一致することがわかります。

SymPyモジュールによる二重階乗の計算

二重階乗は少しマニアックではあるが使われる場面があるので、SymPyモジュールには関数が用意されています。SymPyモジュールでは、階乗はfactorial関数、二重階乗はfactorial2関数を使います。

  1. #10 SymPyモジュールで階乗、二重階乗の計算をする
  2. import sympy
  3. print('10の階乗:',sympy.factorial(10))
  4. print('10の二重階乗:',sympy.factorial2(10))
  5. print('11の二重階乗:',sympy.factorial2(11))

10の階乗: 3628800
10の二重階乗: 3840
11の二重階乗: 10395

前項で計算した結果と一致します。

多重階乗の計算

二重階乗があるとすると三乗階乗もあります。三乗階乗は次の方法で計算します。

$n!!!=n(n-3)(n-6)\cdots1or2or3$

三重階乗はnから3ずつ数を減らして掛け合わせることをいいます。結果的に最後に掛ける数は3で割った余りで、1か2か3になります。

whileループを使った三重階乗を計算する関数

whileループを使う三重階乗の計算も簡単です。6行目でnumを3ずつ減らすように変更するだけです。

  1. #11 whileループで三重階乗を計算する
  2. def factorial3_while(num):
  3. val = 1
  4. while num > 0:
  5. val *= num
  6. num -= 3
  7. return val
  8. print(10, '余り1:', 10*7*4*1, factorial3_while(10))
  9. print(11, '余り2:', 11*8*5*2, factorial3_while(11))
  10. print(12, '余り3:', 12*9*6*3, factorial3_while(12))

10 余り1: 280 280
11 余り2: 880 880
12 余り3: 1944 1944

計算結果は正しいようです。

三重階乗を計算する関数

三重階乗を計算する関数としてSciPyモジュールのspecial.factorialk関数があります。SciPyモジュールには階乗、二重階乗を計算する関数もありますが、factorial(n,k)のようにnのk乗を計算することができます。

  1. #12 scipyモジュールで階乗、k重階乗の計算をする
  2. import scipy.special
  3. print('10の階乗:',scipy.special.factorial(10))
  4. print('10の二重階乗:',scipy.special.factorial2(10))
  5. print('11の二重階乗:',scipy.special.factorial2(11))
  6. print('10の三重階乗:',scipy.special.factorialk(10,3))
  7. print('11の三重階乗:',scipy.special.factorialk(11,3))
  8. print('12の三重階乗:',scipy.special.factorialk(12,3))

10の階乗: 3628800.0
10の二重階乗: 3840.0
11の二重階乗: 10395.0
10の三重階乗: 280

11の三重階乗: 880
12の三重階乗: 1944

上記のように、三重階乗の計算は#12の計算結果と一致します。

多重階乗を計算する

多重階乗があるなら、while文を使った自作関数も多重階乗に対応するようにします。

  1. #13 whileループでn重階乗を計算する
  2. def factorialk_while(num,k):
  3. val = 1
  4. while num > 0:
  5. val *= num
  6. num -= k
  7. return val
  8. limit = 25
  9. for i in range(1,11):
  10. print(i,'重階乗',factorialk_while(limit,i),scipy.special.factorialk(limit,i))

  1. 1行目の関数の定義で、2つ目の引数kを追加します。
  2. 6行目でなnumをkずつ減らすようにします。25のk重階乗を計算するためlimit=25として十重会場まで計算すると、SciPyモジュールとwhile文を使った関数の結果は一致します。

1 重階乗 15511210043330985984000000 15511210043330985984000000
2 重階乗 7905853580625 7905853580625
3 重階乗 608608000 608608000
4 重階乗 5221125 5221125
5 重階乗 375000 375000
6 重階乗 43225 43225
7 重階乗 19800 19800
8 重階乗 3825 3825
9 重階乗 2800 2800
10 重階乗 1875 1875