Python/Ruby/PHP/Golang(Go)で階乗、順列、（重複）組み合わせ

#Python/Ruby/PHP/Golang(Go)で階乗、順列、（重複）組み合わせのパターン数を算出する
確率の計算で必要となる階乗、順列、組み合わせのパターン数。
pythonにはitertools[参考：itertoolsによる順列、組み合わせ、直積のお勉強](http://qiita.com/junkls/items/10384950963056cc8e08)があり、それによりパターンを出せる。
またGolangでは[こういった事例](http://qiita.com/kokardy/items/a18b574d548c212e58e6)にあるように独自の方法でパターンを出している。
ここでは、それぞれのパターン数を算出する単純な方法をPython3、Ruby、PHPとGoLangでそれぞれ記載する。

##階乗（factorial）
1からある数まで連続した整数を順に掛けた積。
例えば、1～5と記載された5枚のカードを１列に並べるときの並べ方の総数は以下の式で計算できる。

```math
5! = 5\times4\times3\times2\times1 = 120
```

##順列（permutation）
解除のときの例では5枚すべて使うことを前提としたが、3枚を利用する場合（重複を許可しない）、以下の式で計算できる。

```math
{}_5\mathrm{ P }_3 = 5\times4\times3 = 60
```

##重複順列（sequence）
ここで、重複を許可する場合は、下記となる。

```math
5^3 = 125
```
Python3のコードでは、代数演算子（**）を利用するだけ。Golangでは`math.Pow(5,3)`といったような方法。

##組み合わせ（combination）
順列のときは並び順を考慮していたが、並び順を考慮しない場合、たとえば5種類の果物から3種類（同一種類は許可しない）選んだ場合の数は、下記の式で計算できる。

```math
{}_5\mathrm{ C }_3 = \frac{5\times4\times3}{3\times2\times1} = 10
```

##重複組み合わせ（repeated combination）
組み合わせのときは、5種類の果物から重複を許可しないで3種類選ぶことを想定していたが、同一種類を許可して、3個の果物を選ぶ（5種類の果物はいずれも3個以上あるものとする）場合、下記の式で計算できる。
数式の`H`は`homogeneous`の意味だと信じている。

```math
{}_5\mathrm{ H }_3 = {}_{5+3-1}\mathrm{ C }_3 = \frac{7\times6\times5}{3\times2\times1} = 35
```

##ソースコード
Python3とGoLang、それぞれで実現してみた。
ただし、都合上`permutation`を先に定義し、最後に重複順列を記載。

###Python3

```py
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)
```

```shell-session:出力結果
60
120
10
35
125
```

###Ruby2.4

```rb
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
```

```shell-session:出力結果
60
120
10
35
125
```

###PHP7.1

```php
<?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);
```

```shell-session:出力結果
60
120
10
35
125
```

###Golang

```go
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))
}
```


```shell-session:出力結果
60
120
10
35
125
```

##その他
重複組み合わせでは5種類の果物はいずれも3個以上あるものとしたが、仮にそれぞれ2個までといった上限がある場合は、上記のいずれの方法でも導出できないので、包除原理を視野に入れる必要がある。
この考えは結構応用が効き、例えば、さいころを3回振り、出た目の総和が12になる場合の数の算出することもできる。
果物をさいころのこの例に紐づけると、それぞれ6個ある3種類の果物から12個取り出す場合の数と同義になる。
この上限のある重複組み合わせをPython3とGo求める方法は[こちら](http://qiita.com/hiroykam/items/3886d6a213cd593fdfab)に記載。