Factorial, permutations, (duplicate) combinations in Python / Ruby / PHP / Golang (Go)

Calculate the number of patterns for factorial, permutation, and (duplicate) combinations in Python / Ruby / PHP / Golang (Go)

The number of factorial, permutation, and combination patterns required to calculate the probability. python has itertools Reference: Permutation, combination, direct product study by itertools, which allows you to create patterns. In addition, Golang uses its own method to create patterns, as shown in Cases like this. Here, a simple method to calculate the number of each pattern is described in Python3, Ruby, PHP and GoLang respectively.

Factorial

A product of sequential integers from 1 to a number. For example, the total number of arrangements when arranging five cards described as 1 to 5 in a row can be calculated by the following formula.

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

Permutation

In the example at the time of cancellation, it was assumed that all 5 cards were used, but when 3 cards are used (duplicates are not allowed), it can be calculated by the following formula.

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

Duplicate sequence

Here, when duplication is permitted, it is as follows.

5^3 = 125

In Python3 code, just use the algebraic operator (**). In Golang, methods like math.Pow (5,3).

Combination

In the case of permutation, the order was taken into consideration, but if the order is not taken into consideration, for example, the number of 3 types of fruits selected from 5 types (the same type is not allowed) can be calculated by the following formula.

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

Repeated combination

When combining, it was supposed to select 3 types from 5 types of fruits without allowing duplication, but allow the same type and select 3 types of fruits (3 or more of each of the 5 types of fruits) If there is), it can be calculated by the following formula. I believe that the formula H means homogeneous.

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

Source code

I tried to realize it with Python3 and GoLang respectively. However, for convenience, permutation is defined first, and the permutations with repetition is described at the end.

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)

Output result


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

Output result


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);

Output result


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

Output result


60
120
10
35
125

Other

In the overlapping combination, it was assumed that there are 3 or more fruits in each of the 5 types, but if there is an upper limit such as 2 each, it cannot be derived by any of the above methods, so it is necessary to consider the inclusion principle. is there. This idea is quite applicable, for example, it is possible to calculate the number when the dice are rolled three times and the total number of rolls is twelve. Linking the fruits to this example of dice is synonymous with the number of 12 fruits taken from each of the 6 fruits of 3 types. See here for how to find this upper limit of duplicate combinations with Python3 and Go.

Recommended Posts

Factorial, permutations, (duplicate) combinations in Python / Ruby / PHP / Golang (Go)
Overlapping combinations with limits in Python / Ruby / PHP / Golang (Go)
Grouping combination in Python / Ruby / PHP / Golang (Go)
Handle prime numbers in Python / Ruby / PHP / Golang (Go)
Duplicate combinations in Python
Find permutations / combinations in Python
Realize PHP / Python generator with Golang / Ruby
[Scraping Summary] | Python Node.js PHP Ruby Go VBA | Scraping Yahoo! Top in 6 languages
GNU GLOBAL (gtags) + α in Go, Ruby, Python
How to handle JSON in Ruby, Python, JavaScript, PHP
Java VS PHP VS Python VS Ruby
About Perl, Python, PHP, Ruby
Combined with permutations in Python
Hello World in various languages [Python / PHP / Java / Perl / Ruby]
Differences between Ruby and Python in scope
Big difference in ruby, python, httpd performance
PHP / Python / Ruby sample hitting Path API
[Itertools.permutations] How to put permutations in Python
Obtaining temporary AWS credentials in PHP, Python
Referencing INI files in Python or Ruby
[Basic grammar] Differences between Ruby / Python / PHP
Enumerate duplicate combinations (C ++) → Add Python code
Try something like Python for-else in Ruby
Duplicate prohibition processing in GAE / Python Datastore
How to write Ruby to_s in Python
Differences in string processing between Python, Ruby, JS, PHP (combination and variable expansion)