Python/Ruby/PHP/Golang(Go)で階乗、順列、（重複）組み合わせのパターン数を算出する
確率の計算で必要となる階乗、順列、組み合わせのパターン数。
pythonにはitertools参考：itertoolsによる順列、組み合わせ、直積のお勉強があり、それによりパターンを出せる。
またGolangではこういった事例にあるように独自の方法でパターンを出している。
ここでは、それぞれのパターン数を算出する単純な方法をPython3、Ruby、PHPとGoLangでそれぞれ記載する。
階乗（factorial）
1からある数まで連続した整数を順に掛けた積。
例えば、1～5と記載された5枚のカードを１列に並べるときの並べ方の総数は以下の式で計算できる。
5! = 5\times4\times3\times2\times1 = 120
順列（permutation）
解除のときの例では5枚すべて使うことを前提としたが、3枚を利用する場合（重複を許可しない）、以下の式で計算できる。
{}_5\mathrm{ P }_3 = 5\times4\times3 = 60
重複順列（sequence）
ここで、重複を許可する場合は、下記となる。
5^3 = 125
Python3のコードでは、代数演算子（**）を利用するだけ。Golangではmath.Pow(5,3)といったような方法。
組み合わせ（combination）
順列のときは並び順を考慮していたが、並び順を考慮しない場合、たとえば5種類の果物から3種類（同一種類は許可しない）選んだ場合の数は、下記の式で計算できる。
{}_5\mathrm{ C }_3 = \frac{5\times4\times3}{3\times2\times1} = 10
重複組み合わせ（repeated combination）
組み合わせのときは、5種類の果物から重複を許可しないで3種類選ぶことを想定していたが、同一種類を許可して、3個の果物を選ぶ（5種類の果物はいずれも3個以上あるものとする）場合、下記の式で計算できる。
数式のHはhomogeneousの意味だと信じている。
{}_5\mathrm{ H }_3 = {}_{5+3-1}\mathrm{ C }_3 = \frac{7\times6\times5}{3\times2\times1} = 35
ソースコード
Python3とGoLang、それぞれで実現してみた。
ただし、都合上permutationを先に定義し、最後に重複順列を記載。
Python3
import functools as ft
def permutation(n, k):
if k > n:
return 0
elif 0 < k <= n:
return ft.reduce(lambda x, y:x * y, [n - v for v in range(k)])
else:
return 1
def factorial(n):
return permutation(n, n - 1)
def combination(n, k):
return int(permutation(n, k) / factorial(k))
def homogeneous(n, k):
return combination(n + k - 1, k)
if __name__ == '__main__':
print(permutation(5, 3))
print(factorial(5))
print(combination(5, 3))
print(homogeneous(5, 3))
print(5 ** 3)
60
120
10
35
125
Ruby2.4
def permutation(n, k)
if k > n
0
elsif 0 < k && k <= n then ((n - k + 1)..n).inject(:*)
else 1
end
end
def factorial(n)
permutation(n, n - 1)
end
def combination(n, k)
(permutation(n, k) / factorial(k)).to_i
end
def homogeneous(n, k)
combination(n + k - 1, k)
end
p permutation(5, 3)
p factorial(5)
p combination(5,3)
p homogeneous(5, 3)
p 5**3
60
120
10
35
125
PHP7.1
<?php
function permutation(int $n, int $k) : int {
if ($k > $n) return 0;
elseif (0 < $k && $k <= $n)
return array_reduce(range($n - $k + 1, $n), function ($c, $v) { return $c *= $v; }, 1);
else return 1;
}
function factorial(int $n) : int {
return permutation($n, $n - 1);
}
function combination(int $n, int $k) : int {
return intval(permutation($n, $k) / factorial($k));
}
function homogeneous(int $n, int $k) : int {
return combination($n + $k - 1, $k);
}
print(permutation(5, 3). PHP_EOL);
print(factorial(5). PHP_EOL);
print(combination(5, 3). PHP_EOL);
print(homogeneous(5, 3). PHP_EOL);
print(5 ** 3);
60
120
10
35
125
Golang
package main;
import (
"fmt"
"math"
)
func permutation(n int, k int) int {
v := 1
if 0 < k && k <= n {
for i := 0; i < k; i++ {
v *= (n - i)
}
} else if k > n {
v = 0
}
return v
}
func factorial(n int) int {
return permutation(n, n - 1)
}
func combination(n int, k int) int {
return permutation(n, k) / factorial(k)
}
func homogeneous(n int, k int) int {
return combination(n + k - 1, k)
}
func main () {
fmt.Printf("%v\n", permutation(5, 3))
fmt.Printf("%v\n", factorial(5))
fmt.Printf("%v\n", combination(5, 3))
fmt.Printf("%v\n", homogeneous(5, 3))
fmt.Printf("%v\n", math.Pow(5, 3))
}
60
120
10
35
125
その他
重複組み合わせでは5種類の果物はいずれも3個以上あるものとしたが、仮にそれぞれ2個までといった上限がある場合は、上記のいずれの方法でも導出できないので、包除原理を視野に入れる必要がある。
この考えは結構応用が効き、例えば、さいころを3回振り、出た目の総和が12になる場合の数の算出することもできる。
果物をさいころのこの例に紐づけると、それぞれ6個ある3種類の果物から12個取り出す場合の数と同義になる。
この上限のある重複組み合わせをPython3とGo求める方法はこちらに記載。