19
17

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2017-05-04

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

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

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個以上あるものとする)場合、下記の式で計算できる。
数式のHhomogeneousの意味だと信じている。

{}_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求める方法はこちらに記載。

19
17
6

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
19
17

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?