Вылічваць і ствараць фактарыялы, перастаноўкі і камбінацыі ў 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(), якая вяртае фактарыял.

• math.factorial(x) — Mathematical functions — Python 3.10.4 Documentation

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

Перастаноўкі — гэта колькасць выпадкаў, калі г выбіраюць з 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.

• scipy.special.perm — SciPy v1.8.0 Reference Guide

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.

• itertools.permutations(iterable, r=None) — Functions creating iterators for efficient looping — Python 3.10.4 Documentation

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

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() не рэалізуе паўтор аргументаў, апісаны ніжэй.

• scipy.special.comb — SciPy v1.8.0 Reference Guide
• scipy.misc.comb — SciPy v0.13.0 Reference Guide

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() – гэта наступны метад.

• Is there a math nCr function in python? – Stack Overflow

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.

• itertools.combinations(iterable, r) — Functions creating iterators for efficient looping — Python 3.10.4 Documentation

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

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

Можна генераваць і пералічваць усе паўтаральныя камбінацыі са спісаў (масіўаў) і г.д., а таксама агульныя лічбы.

Выкарыстоўвайце функцыю kombinacij_with_replacement() у модулі itertools.

• itertools.combinations_with_replacement(iterable, r) — Functions creating iterators for efficient looping — Python 3.10.4 Documentation

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

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

• па тэме:Канкатэнацыя (аб’яднанне) радкоў у Python
• па тэме:Як выкарыстоўваць разуменне спісу Python