Compute and generate factorials, permutations and combinations in Python

Money and Business

The standard module math for mathematical functions in Python can be used to compute factorials. SciPy also has functions to calculate the total number of permutations/combinations.

The itertools module can also be used to generate permutations and combinations from lists (arrays), etc., and enumerate them.

The following is explained here, along with sample code.

  • factorial:math.factorial()
  • Calculate the total number of permutations
    • math.factorial()
    • scipy.special.perm()
  • Generate and enumerate permutations from a list:itertools.permutations()
  • Calculate the total number of combinations
    • math.factorial()
    • scipy.special.comb()
    • How not to use math.factorial()
  • Generate and enumerate combinations from lists:itertools.combinations()
  • Calculate the total number of duplicate combinations
  • Generate and enumerate duplicate combinations from a list:itertools.combinations_with_replacement()

As an example of utilizing permutations, the following is also explained.

  • Create anagrams from strings

If you want to generate a combination of elements of multiple listings instead of a single listing, use itertools.product() in the itertools module.

factorial: math.factorial()

The math module provides a function factorial() that returns the factorial.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Non-integer, negative values will result in a ValueError.

# print(math.factorial(1.5))
# ValueError: factorial() only accepts integral values

# print(math.factorial(-1))
# ValueError: factorial() not defined for negative values

Calculate the total number of permutations

math.factorial()

Permutations are the number of cases where r are chosen from n different ones and placed in a row.

The total number of permutations, p, is obtained by the following equation using factorials.

p = n! / (n - r)!

It can be calculated as follows using the function math.factorial(), which returns the factorial. The ⌘ operator, which performs integer division, is used to return an integer type.

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

print(permutations_count(4, 2))
# 12

print(permutations_count(4, 4))
# 24

scipy.special.perm()

SciPy provides a function scipy.special.perm() that returns the total number of permutations. A separate SciPy installation is required. Available from version 0.14.0.

from scipy.special import perm

print(perm(4, 2))
# 12.0

print(perm(4, 2, exact=True))
# 12

print(perm(4, 4, exact=True))
# 24

exact=False
The third argument is set as above by default and returns a floating point number. Note that if you want to get it as an integer, you need to set it as follows.
exact=True

Note that only “import scipy” will not load the scipy.special module.

Execute perm() as “from scipy.special import perm” as in the above example, or execute scipy.special.perm() as “import scipy.special”.

Generate and enumerate permutations from a list: itertools.permutations()

Not only total numbers, but also permutations can be generated and enumerated from lists (arrays), etc.

Use the permutations() function of the itertools module.

Passing an iterable (list or set type) as the first argument and the number of pieces to be selected as the second argument returns an iterator for that permutation.

import itertools

l = ['a', 'b', 'c', 'd']

p = itertools.permutations(l, 2)

print(type(p))
# <class 'itertools.permutations'>

To enumerate all of them, you can use a for loop.

for v in itertools.permutations(l, 2):
    print(v)
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'a')
# ('b', 'c')
# ('b', 'd')
# ('c', 'a')
# ('c', 'b')
# ('c', 'd')
# ('d', 'a')
# ('d', 'b')
# ('d', 'c')

Since it is a finite iterator, it can also be converted to a list type with list().

When the number of elements in the list is obtained with len(), it can be confirmed that it matches the total number of permutations calculated from the factorial.

p_list = list(itertools.permutations(l, 2))

print(p_list)
# [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('d', 'b'), ('d', 'c')]

print(len(p_list))
# 12

If the second argument is omitted, the permutation for selecting all elements is returned.

for v in itertools.permutations(l):
    print(v)
# ('a', 'b', 'c', 'd')
# ('a', 'b', 'd', 'c')
# ('a', 'c', 'b', 'd')
# ('a', 'c', 'd', 'b')
# ('a', 'd', 'b', 'c')
# ('a', 'd', 'c', 'b')
# ('b', 'a', 'c', 'd')
# ('b', 'a', 'd', 'c')
# ('b', 'c', 'a', 'd')
# ('b', 'c', 'd', 'a')
# ('b', 'd', 'a', 'c')
# ('b', 'd', 'c', 'a')
# ('c', 'a', 'b', 'd')
# ('c', 'a', 'd', 'b')
# ('c', 'b', 'a', 'd')
# ('c', 'b', 'd', 'a')
# ('c', 'd', 'a', 'b')
# ('c', 'd', 'b', 'a')
# ('d', 'a', 'b', 'c')
# ('d', 'a', 'c', 'b')
# ('d', 'b', 'a', 'c')
# ('d', 'b', 'c', 'a')
# ('d', 'c', 'a', 'b')
# ('d', 'c', 'b', 'a')

print(len(list(itertools.permutations(l))))
# 24

In itertools.permutations(), elements are treated based on position, not value. Duplicate values are not taken into account.

l = ['a', 'a']

for v in itertools.permutations(l, 2):
    print(v)
# ('a', 'a')
# ('a', 'a')

The same applies to the following functions, described below.

  • itertools.combinations()
  • itertools.combinations_with_replacement()

Calculate the total number of combinations

math.factorial()

The number of combinations is the number of r pieces to choose from n different pieces. The order is not considered as in permutations.

The total number of combinations c is obtained by the following equation.

c = n! / (r! * (n - r)!)

It can be calculated as follows using the function math.factorial(), which returns the factorial. The ⌘ operator, which performs integer division, is used to return an integer type.

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

print(combinations_count(4, 2))
# 6

scipy.special.comb()

SciPy provides a function scipy.special.comb() that returns the total number of permutations. A separate SciPy installation is required. Available from version 0.14.0. Note that scipy.misc.comb() does not implement the argument repetition described below.

from scipy.special import comb

print(comb(4, 2))
# 6.0

print(comb(4, 2, exact=True))
# 6

print(comb(4, 0, exact=True))
# 1

exact=False
As with scipy.special.perm(), the third argument is set as above by default and returns a floating-point number. Note that if you want to get it as an integer, you need to set it as follows.
exact=True
The total number of duplicate combinations can also be obtained with the fourth argument, repetition. This is described below.

Again, note that only “import scipy” will not load the scipy.special module.

As in the above example, execute comb() as “from scipy.special import comb” or execute scipy.special.comb() as “import scipy.special”. The same applies to “scipy.misc”.

How not to use math.factorial()

Another method that uses only the standard library and is faster than the method using math.factorial() is the following method.

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

print(combinations_count(4, 2))
# 6

print(combinations_count(4, 0))
# 1

Generate and enumerate combinations from lists: itertools.combinations()

It is possible to generate and enumerate all combinations from lists (arrays), etc. as well as total numbers.

Use the combinations() function of the itertools module.

Passing an iterable (list or set type) as the first argument and the number of pieces to be selected as the second argument returns the iterator for that combination.

l = ['a', 'b', 'c', 'd']

c = itertools.combinations(l, 2)

print(type(c))
# <class 'itertools.combinations'>

for v in itertools.combinations(l, 2):
    print(v)
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'c')
# ('b', 'd')
# ('c', 'd')

c_list = list(itertools.combinations(l, 2))

print(c_list)
# [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

print(len(c_list))
# 6

Calculate the total number of duplicate combinations

The number of duplicate combinations is the number of cases in which r are chosen from n different ones, allowing for duplicates.

The total number of duplicate combinations is equal to the number of combinations to choose (r) out of (n + r – 1) different ones.

Therefore, we can use the function defined above to calculate the total number of combinations.

def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)

print(combinations_with_replacement_count(4, 2))
# 10

In “scipy.special.comb()” described above, the total number of duplicate combinations can be obtained by setting the fourth argument “repetition=True.
Note that the argument “repetition” is not implemented in “scipy.misc.comb()” in versions prior to “SciPy0.14.0”.

from scipy.special import comb

print(comb(4, 2, exact=True, repetition=True))
# 10

Generate and enumerate duplicate combinations from a list: itertools.combinations_with_replacement()

It is possible to generate and enumerate all duplicate combinations from lists (arrays), etc. as well as total numbers.

Use the combinations_with_replacement() function in the itertools module.

Passing an iterable (list or set type) as the first argument and the number of pieces to be selected as the second argument returns an iterator for that overlapping combination.

h = itertools.combinations_with_replacement(l, 2)

print(type(h))
# <class 'itertools.combinations_with_replacement'>

for v in itertools.combinations_with_replacement(l, 2):
    print(v)
# ('a', 'a')
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'b')
# ('b', 'c')
# ('b', 'd')
# ('c', 'c')
# ('c', 'd')
# ('d', 'd')

h_list = list(itertools.combinations_with_replacement(l, 2))

print(h_list)
# [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'b'), ('b', 'c'), ('b', 'd'), ('c', 'c'), ('c', 'd'), ('d', 'd')]

print(len(h_list))
# 10

Create anagrams from strings

Itertools.permutations() makes it easy to create string permutations (anagrams).

s = 'arc'

for v in itertools.permutations(s):
    print(v)
# ('a', 'r', 'c')
# ('a', 'c', 'r')
# ('r', 'a', 'c')
# ('r', 'c', 'a')
# ('c', 'a', 'r')
# ('c', 'r', 'a')

To combine a tuple of one character at a time into a string and make it into a list, do the following

anagram_list = [''.join(v) for v in itertools.permutations(s)]

print(anagram_list)
# ['arc', 'acr', 'rac', 'rca', 'car', 'cra']

The join() method, which concatenates elements of a list or tuple into a string, and the list comprehension notation are used.

Copied title and URL