Obliczanie i generowanie współczynników, permutacji i kombinacji w Pythonie

Biznes

Do obliczania współczynników można użyć standardowego modułu math dla funkcji matematycznych w Pythonie. W SciPy dostępne są również funkcje do obliczania całkowitej liczby permutacji i kombinacji.

Moduł itertools może być także używany do generowania permutacji i kombinacji z list (tablic) itp. oraz ich wyliczania.

Objaśniono tu następujące zagadnienia wraz z przykładowym kodem.

  • silnia:math.factorial()
  • Oblicz całkowitą liczbę permutacji
    • math.factorial()
    • scipy.special.perm()
  • Generowanie i wyliczanie permutacji z listy:itertools.permutations()
  • Oblicz całkowitą liczbę kombinacji
    • math.factorial()
    • scipy.special.comb()
    • Jak nie używać funkcji math.factorial()
  • Generowanie i wyliczanie kombinacji z list:itertools.combinations()
  • Oblicz całkowitą liczbę zduplikowanych kombinacji
  • Generowanie i wyliczanie kombinacji duplikatów z listy:itertools.combinations_with_replacement()

Jako przykład wykorzystania permutacji wyjaśniono również, co następuje.

  • Tworzenie anagramów z ciągów znaków

Jeśli chcesz wygenerować kombinację elementów z wielu zestawień zamiast pojedynczego zestawienia, użyj funkcji itertools.product() w module itertools.

silnia: math.factorial()

Moduł matematyczny udostępnia funkcję factorial(), która zwraca czynnik.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Niecałkowite, ujemne wartości spowodują wystąpienie błędu ValueError.

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

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

Oblicz całkowitą liczbę permutacji

math.factorial()

Permutacje to liczba przypadków, w których r jest wybrane z n różnych i umieszczone w rzędzie.

Całkowitą liczbę permutacji, p, można otrzymać za pomocą następującego równania z zastosowaniem współczynników.

p = n! / (n - r)!

Można go obliczyć w następujący sposób, korzystając z funkcji math.factorial(), która zwraca czynnik. Operator ⌘, który wykonuje dzielenie liczb całkowitych, jest używany do zwracania typu całkowitego.

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 udostępnia funkcję scipy.special.perm(), która zwraca całkowitą liczbę permutacji. Wymagana jest osobna instalacja SciPy. Dostępne od wersji 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
Trzeci argument jest domyślnie ustawiony jak powyżej i zwraca liczbę zmiennoprzecinkową. Jeśli chcesz otrzymać liczbę całkowitą, musisz ją ustawić w następujący sposób.
exact=True

Należy zauważyć, że samo „import scipy” nie spowoduje załadowania modułu scipy.special.

Wykonaj perm() jako „from scipy.special import perm”, jak w powyższym przykładzie, lub wykonaj scipy.special.perm() jako „import scipy.special”.

Generowanie i wyliczanie permutacji z listy: itertools.permutations()

Na podstawie list (tablic) można generować i wyliczać nie tylko liczby całkowite, ale także permutacje itp.

Użyj funkcji permutations() z modułu itertools.

Przekazanie iterowalnej (typu lista lub zbiór) jako pierwszego argumentu oraz liczby elementów do wybrania jako drugiego argumentu zwraca iterator dla tej permutacji.

import itertools

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

p = itertools.permutations(l, 2)

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

Aby wyliczyć je wszystkie, można użyć pętli 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')

Ponieważ jest to skończony iterator, można go również przekonwertować na typ listy za pomocą funkcji list().

Po uzyskaniu liczby elementów na liście za pomocą funkcji len() można potwierdzić, że jest ona zgodna z całkowitą liczbą permutacji obliczoną na podstawie czynnika.

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

Jeśli drugi argument zostanie pominięty, zwracana jest permutacja umożliwiająca wybranie wszystkich elementów.

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

W itertools.permutations() elementy są traktowane na podstawie pozycji, a nie wartości. Duplikaty wartości nie są brane pod uwagę.

l = ['a', 'a']

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

To samo dotyczy następujących funkcji, opisanych poniżej.

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

Oblicz całkowitą liczbę kombinacji

math.factorial()

Liczba kombinacji to liczba r elementów do wyboru spośród n różnych elementów. Kolejność nie jest brana pod uwagę, tak jak w przypadku permutacji.

Całkowitą liczbę kombinacji c uzyskuje się za pomocą następującego równania.

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

Można go obliczyć w następujący sposób, korzystając z funkcji math.factorial(), która zwraca czynnik. Operator ⌘, który wykonuje dzielenie liczb całkowitych, jest używany do zwracania typu całkowitego.

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 udostępnia funkcję scipy.special.comb(), która zwraca całkowitą liczbę permutacji. Wymagana jest osobna instalacja SciPy. Dostępna od wersji 0.14.0. Zwróć uwagę, że scipy.misc.comb() nie implementuje opisanego poniżej powtarzania argumentów.

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
Podobnie jak w przypadku scipy.special.perm(), trzeci argument jest domyślnie ustawiony jak powyżej i zwraca liczbę zmiennoprzecinkową. Zauważ, że jeśli chcesz otrzymać ją jako liczbę całkowitą, musisz ustawić ją w następujący sposób.
exact=True
Całkowitą liczbę zduplikowanych kombinacji można również uzyskać za pomocą czwartego argumentu – powtórzenia. Opisano to poniżej.

Ponownie zauważ, że tylko „import scipy” nie spowoduje załadowania modułu scipy.special.

Tak jak w powyższym przykładzie, wykonaj comb() jako „from scipy.special import comb” lub wykonaj scipy.special.comb() jako „import scipy.special”. To samo dotyczy funkcji „scipy.misc”.

Jak nie używać funkcji math.factorial()

Inną metodą, która korzysta tylko z biblioteki standardowej i jest szybsza niż metoda wykorzystująca math.factorial(), jest następująca metoda.

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

Generowanie i wyliczanie kombinacji z list: itertools.combinations()

Możliwe jest generowanie i wyliczanie wszystkich kombinacji z list (tablic) itp. oraz liczb całkowitych.

Użyj funkcji combinations() z modułu itertools.

Przekazanie iterowalnej (typu lista lub zbiór) jako pierwszego argumentu oraz liczby elementów do wybrania jako drugiego argumentu zwraca iterator dla tej kombinacji.

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

Oblicz całkowitą liczbę zduplikowanych kombinacji

Liczba zduplikowanych kombinacji to liczba przypadków, w których wybrano r spośród n różnych, z uwzględnieniem duplikatów.

Całkowita liczba zduplikowanych kombinacji jest równa liczbie kombinacji do wyboru (r) spośród (n + r – 1) różnych kombinacji.

Dlatego do obliczenia całkowitej liczby kombinacji można użyć funkcji zdefiniowanej powyżej.

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

print(combinations_with_replacement_count(4, 2))
# 10

W opisanej powyżej funkcji „scipy.special.comb()” całkowitą liczbę zduplikowanych kombinacji można uzyskać, ustawiając czwarty argument „repetition=True”.
Zwróć uwagę, że argument „repetition” nie jest zaimplementowany w funkcji „scipy.misc.comb()” w wersjach wcześniejszych niż „SciPy0.14.0”.

from scipy.special import comb

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

Generowanie i wyliczanie kombinacji duplikatów z listy: itertools.combinations_with_replacement()

Możliwe jest generowanie i wyliczanie wszystkich zduplikowanych kombinacji z list (tablic) itp. oraz liczb całkowitych.

Użyj funkcji combinations_with_replacement() w module itertools.

Przekazanie iterowalnej (typu lista lub zbiór) jako pierwszego argumentu oraz liczby elementów do wybrania jako drugiego argumentu zwraca iterator dla tej nakładającej się kombinacji.

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

Tworzenie anagramów z ciągów znaków

Itertools.permutations() ułatwia tworzenie permutacji łańcuchów (anagramów).

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

Aby połączyć krotkę składającą się z jednego znaku w ciąg znaków i przekształcić ją w listę, wykonaj następujące czynności

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

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

Używana jest metoda join(), która konkatenuje elementy listy lub krotki w łańcuch, oraz notacja list comprehension.