Обчислюйте та генеруйте факториали, перестановки та комбінації в Python

Бізнес

Стандартний модуль математики для математичних функцій у 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

Зауважте, що тільки «імпорт scipy» не завантажить модуль scipy.special.

Виконайте perm() як “з scipy.special import perm”, як у наведеному вище прикладі, або запустіть scipy.special.perm() як “import scipy.special”.

Створення та перерахування перестановок зі списку:itertools.permutations()

Зі списків (масивів) можна генерувати та перераховувати не тільки загальні числа, а й перестановки.

Використовуйте функцію permutations() модуля itertools.

Передача ітераційного типу (типу списку або набору) як першого аргументу та кількості частин, які потрібно вибрати як другий аргумент, повертає ітератор для цієї перестановки.

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
Загальну кількість повторюваних комбінацій також можна отримати за допомогою четвертого аргументу, повторення. Це описано нижче.

Знову зауважте, що тільки «імпорт scipy» не завантажить модуль scipy.special.

Як і в наведеному вище прикладі, виконайте comb() як “з 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()

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

Використовуйте функцію комбінацій() модуля itertools.

Передача ітерації (типу списку або набору) як першого аргументу та кількості частин, які потрібно вибрати як другий аргумент, повертає ітератор для цієї комбінації.

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

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

Використовуйте функцію Kombins_with_replacement() у модулі itertools.

Передача ітерації (типу списку або набору) як першого аргументу та кількості частин, які потрібно вибрати як другий аргумент, повертає ітератор для цієї комбінації, що перекривається.

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(), який об’єднує елементи списку або кортежу в рядок, і нотація розуміння списку.