Izračunajte i generirajte faktorijele, permutacije i kombinacije u Pythonu

Poslovanje

Standardna modulska matematika za matematičke funkcije u Pythonu može se koristiti za izračunavanje faktorijala. SciPy također ima funkcije za izračunavanje ukupnog broja permutacija/kombinacija.

Modul itertools također se može koristiti za generiranje permutacija i kombinacija iz popisa (nizova) itd., te za njihovo nabrajanje.

Ovdje je objašnjeno sljedeće, zajedno s uzorkom koda.

  • faktorijel:math.factorial()
  • Izračunajte ukupan broj permutacija
    • math.factorial()
    • scipy.special.perm()
  • Generirajte i nabrojite permutacije s popisa:itertools.permutations()
  • Izračunajte ukupan broj kombinacija
    • math.factorial()
    • scipy.special.comb()
    • Kako ne koristiti math.factorial()
  • Generirajte i nabrajajte kombinacije s popisa:itertools.combinations()
  • Izračunajte ukupan broj duplikata kombinacija
  • Generirajte i nabrojite duple kombinacije s popisa:itertools.combinations_with_replacement()

Kao primjer korištenja permutacija, također je objašnjeno sljedeće.

  • Izradite anagrame od nizova

Ako želite generirati kombinaciju elemenata višestrukih unosa umjesto jednog unosa, koristite itertools.product() u modulu itertools.

faktorijel:math.factorial()

Matematički modul pruža funkciju factorial() koja vraća faktorijel.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Necijelobrojne negativne vrijednosti rezultirat će ValueError.

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

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

Izračunajte ukupan broj permutacija

math.factorial()

Permutacije su broj slučajeva u kojima se r bira između n različitih i postavlja u red.

Ukupni broj permutacija, p, dobiva se sljedećom jednadžbom pomoću faktorijala.

p = n! / (n - r)!

Može se izračunati na sljedeći način pomoću funkcije math.factorial(), koja vraća faktorijel. Operator ⌘, koji obavlja cjelobrojnu dijeljenje, koristi se za vraćanje cjelobrojnog tipa.

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 pruža funkciju scipy.special.perm() koja vraća ukupan broj permutacija. Potrebna je zasebna instalacija SciPy. Dostupno od verzije 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
Treći argument je prema zadanim postavkama postavljen kao gore i vraća broj s pomičnim zarezom. Imajte na umu da ako ga želite dobiti kao cijeli broj, morate ga postaviti na sljedeći način.
exact=True

Imajte na umu da samo “import scipy” neće učitati scipy.special modul.

Izvršite perm() kao “iz scipy.special import perm” kao u gornjem primjeru ili izvršite scipy.special.perm() kao “import scipy.special”.

Generirajte i nabrojite permutacije s popisa:itertools.permutations()

Ne samo ukupni brojevi, već i permutacije mogu se generirati i nabrajati iz popisa (nizova) itd.

Koristite funkciju permutations() modula itertools.

Prosljeđivanje iterable (vrste popisa ili skupa) kao prvog argumenta i broja dijelova koji se odabiru kao drugi argument vraća iterator za tu permutaciju.

import itertools

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

p = itertools.permutations(l, 2)

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

Da biste ih sve nabrojali, možete koristiti for petlju.

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

Budući da je konačan iterator, također se može pretvoriti u tip popisa pomoću liste().

Kada se broj elemenata na popisu dobije pomoću len(), može se potvrditi da se podudara s ukupnim brojem permutacija izračunatim iz faktorijala.

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

Ako je drugi argument izostavljen, vraća se permutacija za odabir svih elemenata.

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

U itertools.permutations(), elementi se tretiraju na temelju položaja, a ne vrijednosti. Duplicirane vrijednosti se ne uzimaju u obzir.

l = ['a', 'a']

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

Isto vrijedi i za sljedeće funkcije, opisane u nastavku.

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

Izračunajte ukupan broj kombinacija

math.factorial()

Broj kombinacija je broj r komada za odabir između n različitih komada. Redoslijed se ne smatra kao u permutacijama.

Ukupan broj kombinacija c dobiva se sljedećom jednadžbom.

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

Može se izračunati na sljedeći način pomoću funkcije math.factorial(), koja vraća faktorijel. Operator ⌘, koji obavlja cjelobrojnu dijeljenje, koristi se za vraćanje cjelobrojnog tipa.

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 pruža funkciju scipy.special.comb() koja vraća ukupan broj permutacija. Potrebna je zasebna instalacija SciPy. Dostupno od verzije 0.14.0. Imajte na umu da scipy.misc.comb() ne implementira dolje opisano ponavljanje argumenata.

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
Kao i kod scipy.special.perm(), treći argument je prema zadanim postavkama postavljen kao gore i vraća broj s pomičnim zarezom. Imajte na umu da ako ga želite dobiti kao cijeli broj, morate ga postaviti na sljedeći način.
exact=True
Ukupan broj duplikata kombinacija također se može dobiti s četvrtim argumentom, ponavljanjem. Ovo je opisano u nastavku.

Opet, imajte na umu da samo “import scipy” neće učitati scipy.special modul.

Kao u gornjem primjeru, izvršite comb() kao “iz scipy.special import comb” ili izvršite scipy.special.comb() kao “import scipy.special”. Isto vrijedi i za “scipy.misc”.

Kako ne koristiti math.factorial()

Druga metoda koja koristi samo standardnu ​​biblioteku i brža je od metode koja koristi math.factorial() je sljedeća 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

Generirajte i nabrajajte kombinacije s popisa:itertools.combinations()

Moguće je generirati i nabrajati sve kombinacije iz popisa (nizova) itd. kao i ukupne brojeve.

Koristite funkciju kombinacije() modula itertools.

Prosljeđivanje iterable (vrste popisa ili skupa) kao prvog argumenta i broja dijelova koji se odabiru kao drugi argument vraća iterator za tu kombinaciju.

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

Izračunajte ukupan broj duplikata kombinacija

Broj duplikata kombinacija je broj slučajeva u kojima se r bira između n različitih, dopuštajući duplikate.

Ukupni broj duplikata kombinacija jednak je broju kombinacija za odabir (r) od (n + r – 1) različitih.

Stoga možemo koristiti gore definiranu funkciju za izračunavanje ukupnog broja kombinacija.

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

print(combinations_with_replacement_count(4, 2))
# 10

U gore opisanom “scipy.special.comb()”, ukupan broj duplikata kombinacija može se dobiti postavljanjem četvrtog argumenta “repetition=True.
Imajte na umu da argument “ponavljanje” nije implementiran u “scipy.misc.comb()” u verzijama prije “SciPy0.14.0”.

from scipy.special import comb

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

Generirajte i nabrojite duple kombinacije s popisa:itertools.combinations_with_replacement()

Moguće je generirati i nabrajati sve duple kombinacije iz popisa (nizova) itd. kao i ukupne brojeve.

Upotrijebite funkciju kombinacije_with_replacement() u modulu itertools.

Prosljeđivanje iterable (vrste popisa ili skupa) kao prvog argumenta i broja dijelova koji se odabiru kao drugi argument vraća iterator za tu kombinaciju preklapanja.

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

Izradite anagrame od nizova

Itertools.permutations() olakšava stvaranje permutacija nizova (anagrama).

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

Da biste spojili torku od jednog po jednog znaka u niz i pretvorili ga u popis, učinite sljedeće

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

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

Koriste se metoda join() koja spaja elemente popisa ili tuple u niz i zapis razumijevanja popisa.