Вычисление и генерация факториалов, перестановок и комбинаций в Python

Бизнес

Стандартный модуль math для математических функций в Python может быть использован для вычисления факториалов. В SciPy также есть функции для подсчета общего числа перестановок\комбинаций.

Модуль itertools также можно использовать для генерации перестановок и комбинаций из списков (массивов) и т.д. и их перечисления.

Ниже приводится пояснение, а также пример кода.

  • факториал:math.factorial()
  • Вычислите общее количество перестановок
    • math.factorial()
    • scipy.special.perm()
  • Генерация и перечисление перестановок из списка:itertools.permutations()
  • Подсчитайте общее количество комбинаций
    • math.factorial()
    • scipy.special.comb()
    • Как не следует использовать math.factorial()
  • Генерировать и перечислять комбинации из списков:itertools.combinations()
  • Подсчитайте общее количество дублирующих комбинаций
  • Генерация и перечисление дублирующих комбинаций из списка:itertools.combinations_with_replacement()

В качестве примера использования перестановок можно привести следующее.

  • Создание анаграмм из строк

Если вы хотите сгенерировать комбинацию элементов нескольких объявлений вместо одного объявления, используйте itertools.product() в модуле itertools.

факториал: math.factorial()

Модуль математики предоставляет функцию factorial(), которая возвращает факториал.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Нецелые, отрицательные значения приведут к ошибке ValueError.

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

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

Вычислите общее количество перестановок

math.factorial()

Перестановки — это количество случаев, когда r выбираются из n различных и располагаются в ряд.

Общее количество перестановок, p, получается из следующего уравнения с использованием факториалов.

p = n! / (n - r)!

Его можно вычислить следующим образом с помощью функции math.factorial(), которая возвращает факториал. Оператор ⌘, выполняющий целочисленное деление, используется для возврата целого типа.

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 предоставляет функцию scipy.special.perm(), которая возвращает общее количество перестановок. Требуется отдельная установка SciPy. Доступна начиная с версии 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
Третий аргумент по умолчанию задан как указано выше и возвращает число с плавающей точкой. Обратите внимание, что если вы хотите получить его как целое число, вам нужно задать его следующим образом.
exact=True

Обратите внимание, что только «import scipy» не загрузит модуль scipy.special.

Выполните perm() как «from scipy.special import perm», как в примере выше, или выполните scipy.special.perm() как «import scipy.special».

Генерация и перечисление перестановок из списка: itertools.permutations()

Из списков (массивов) можно генерировать и перечислять не только общие числа, но и перестановки и т.д.

Используйте функцию permutations() модуля itertools.

Передача итератора (типа list или set) в качестве первого аргумента и количества частей, которые нужно выбрать, в качестве второго аргумента возвращает итератор для данной перестановки.

import itertools

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

p = itertools.permutations(l, 2)

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

Чтобы перечислить их все, можно использовать цикл for.

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

Поскольку это конечный итератор, его также можно преобразовать в тип списка с помощью функции list().

Когда количество элементов в списке получено с помощью len(), можно убедиться, что оно совпадает с общим количеством перестановок, вычисленным по факториалу.

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

Если второй аргумент опущен, возвращается перестановка для выбора всех элементов.

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

В itertools.permutations() элементы обрабатываются на основе позиции, а не значения. Дублирующиеся значения не учитываются.

l = ['a', 'a']

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

То же самое относится и к следующим функциям, описанным ниже.

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

Подсчитайте общее количество комбинаций

math.factorial()

Число комбинаций — это число r фигур, которые можно выбрать из n различных фигур. Порядок не учитывается, как в перестановках.

Общее количество комбинаций c получается из следующего уравнения.

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

Его можно вычислить следующим образом с помощью функции math.factorial(), которая возвращает факториал. Оператор ⌘, выполняющий целочисленное деление, используется для возврата целого типа.

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 предоставляет функцию scipy.special.comb(), которая возвращает общее количество перестановок. Требуется отдельная установка SciPy. Доступна начиная с версии 0.14.0. Обратите внимание, что scipy.misc.comb() не реализует повторение аргументов, описанное ниже.

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
Как и в scipy.special.perm(), третий аргумент по умолчанию задается как указано выше и возвращает число с плавающей точкой. Обратите внимание, что если вы хотите получить его как целое число, вам нужно задать его следующим образом.
exact=True
Общее количество дублирующих комбинаций можно также получить с помощью четвертого аргумента — повторения. Это описано ниже.

Опять же, обратите внимание, что только «import scipy» не загрузит модуль scipy.special.

Как в примере выше, выполните comb() как «from scipy.special import comb» или выполните scipy.special.comb() как «import scipy.special». То же самое относится и к «scipy.misc».

Как не следует использовать math.factorial()

Другой метод, использующий только стандартную библиотеку и более быстрый, чем метод с использованием math.factorial(), — это следующий метод.

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

Генерировать и перечислять комбинации из списков: itertools.combinations()

Можно генерировать и перечислять все комбинации из списков (массивов) и т.д., а также общие числа.

Используйте функцию combinations() модуля itertools.

Передача итератора (типа list или set) в качестве первого аргумента и количества частей, которые нужно выбрать, в качестве второго аргумента возвращает итератор для этой комбинации.

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

Подсчитайте общее количество дублирующих комбинаций

Число дублирующих комбинаций — это число случаев, в которых r выбирается из n различных комбинаций с учетом дубликатов.

Общее количество дублирующих комбинаций равно количеству комбинаций для выбора (r) из (n + r — 1) различных комбинаций.

Поэтому мы можем использовать функцию, определенную выше, для подсчета общего количества комбинаций.

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

print(combinations_with_replacement_count(4, 2))
# 10

В «scipy.special.comb()», описанном выше, общее количество дублирующих комбинаций можно получить, задав четвертый аргумент «repetition=True».
Обратите внимание, что аргумент «повторение» не реализован в «scipy.misc.comb()» в версиях до «SciPy0.14.0».

from scipy.special import comb

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

Генерация и перечисление дублирующих комбинаций из списка: itertools.combinations_with_replacement()

Можно генерировать и перечислять все дублирующие комбинации из списков (массивов) и т.д., а также общие числа.

Используйте функцию combinations_with_replacement() в модуле itertools.

Передача итератора (типа list или set) в качестве первого аргумента и количества частей, которые нужно выбрать, в качестве второго аргумента возвращает итератор для этой перекрывающейся комбинации.

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

Создание анаграмм из строк

Itertools.permutations() позволяет легко создавать перестановки строк (анаграммы).

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

Чтобы объединить кортеж из одного символа за раз в строку и превратить ее в список, сделайте следующее

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

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

Используется метод join(), который объединяет элементы списка или кортежа в строку, и нотация понимания списка.