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

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


『 Go 』Article List
Category List

Eye Catch Image
Read More

Androidに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

AWSに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Bitcoinに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

CentOSに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

dockerに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

GitHubに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Goに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Javaに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

JavaScriptに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Laravelに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Pythonに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Rubyに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Scalaに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Swiftに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Unityに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Vue.jsに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Wordpressに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

機械学習に関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。