Изчисляване и генериране на факториали, пермутации и комбинации в 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()

Модулът math предоставя функцията 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.

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

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.

При подаване на итератор (тип списък или набор) като първи аргумент и броя на елементите, които трябва да бъдат избрани, като втори аргумент, се връща итераторът за тази комбинация.

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.

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

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

Copied title and URL