Bereken en genereer factorials, permutaties en combinaties in Python

Bedrijf

De standaardmodule math voor wiskundige functies in Python kan worden gebruikt om factorialen te berekenen. SciPy heeft ook functies om het totale aantal permutaties te berekenen.

De module itertools kan ook worden gebruikt om permutaties en combinaties te genereren uit lijsten (arrays), enz. en ze op te sommen.

Het volgende wordt hier uitgelegd, samen met voorbeeldcode.

  • factorial:math.factorial()
  • Bereken het totaal aantal permutaties
    • math.factorial()
    • scipy.special.perm()
  • Genereren en opsommen van permutaties uit een lijst:itertools.permutations()
  • Bereken het totaal aantal combinaties
    • math.factorial()
    • scipy.special.comb()
    • Hoe math.factorial() niet te gebruiken
  • Genereren en opsommen van combinaties uit lijsten:itertools.combinations()
  • Bereken het totaal aantal duplicaatcombinaties
  • Duplicaatcombinaties uit een lijst genereren en opsommen:itertools.combinations_with_replacement()

Als voorbeeld van het gebruik van permutaties, wordt ook het volgende uitgelegd.

  • Maak anagrammen van strings

Als je een combinatie van elementen van meerdere lijsten wilt genereren in plaats van een enkele lijst, gebruik dan itertools.product() in de itertools module.

factorial: math.factorial()

De wiskunde module heeft een functie factorial() die de factorie teruggeeft.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Niet-integer, negatieve waarden zullen resulteren in een ValueError.

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

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

Bereken het totaal aantal permutaties

math.factorial()

Permutaties zijn het aantal gevallen waarin r uit n verschillende worden gekozen en in een rij worden geplaatst.

Het totaal aantal permutaties, p, wordt verkregen door de volgende vergelijking met behulp van factorials.

p = n! / (n - r)!

Het kan als volgt berekend worden met de functie math.factorial(), die de factorial teruggeeft. De operator ⌘, die een gehele deling uitvoert, wordt gebruikt om een geheel getal terug te geven.

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 levert een functie scipy.special.perm() die het totale aantal permutaties teruggeeft. Een afzonderlijke SciPy-installatie is vereist. Beschikbaar vanaf versie 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
Het derde argument is standaard ingesteld zoals hierboven en geeft een drijvend komma getal. Merk op dat indien u het als een geheel getal wenst te bekomen, u het als volgt dient in te stellen.
exact=True

Merk op dat alleen “import scipy” de speciale module scipy.special niet zal laden.

Voer perm() uit als “from scipy.special import perm” zoals in het bovenstaande voorbeeld, of voer scipy.special.perm() uit als “import scipy.special”.

Genereren en opsommen van permutaties uit een lijst: itertools.permutations()

Niet alleen totale getallen, maar ook permutaties kunnen worden gegenereerd en opgesomd uit lijsten (arrays), enz.

Gebruik de permutaties() functie van de itertools module.

Door een iterabel (lijst of verzameling) als eerste argument en het aantal te selecteren stukken als tweede argument mee te geven, wordt een iterator voor die permutatie verkregen.

import itertools

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

p = itertools.permutations(l, 2)

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

Om ze allemaal op te sommen, kun je een for-lus gebruiken.

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

Aangezien het een eindige iterator is, kan het ook geconverteerd worden naar een lijsttype met list().

Wanneer het aantal elementen in de lijst verkregen is met len(), kan bevestigd worden dat het overeenkomt met het totaal aantal permutaties berekend uit de factorial.

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

Indien het tweede argument wordt weggelaten, wordt de permutatie voor de selectie van alle elementen teruggegeven.

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

In itertools.permutations(), worden elementen behandeld op basis van positie, niet waarde. Duplicaatwaarden worden niet in rekening gebracht.

l = ['a', 'a']

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

Hetzelfde geldt voor de volgende functies, die hieronder worden beschreven.

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

Bereken het totaal aantal combinaties

math.factorial()

Het aantal combinaties is het aantal r stukken te kiezen uit n verschillende stukken. De volgorde wordt niet in rekening gebracht zoals bij permutaties.

Het totaal aantal combinaties c wordt verkregen met de volgende vergelijking.

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

Het kan als volgt berekend worden met de functie math.factorial(), die de factorial teruggeeft. De operator ⌘, die een gehele deling uitvoert, wordt gebruikt om een geheel getal terug te geven.

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 levert een functie scipy.special.comb() die het totale aantal permutaties teruggeeft. Een afzonderlijke SciPy-installatie is vereist. Beschikbaar vanaf versie 0.14.0. Merk op dat scipy.misc.comb() de hieronder beschreven argumentherhaling niet implementeert.

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
Net zoals bij scipy.special.perm(), is het derde argument standaard ingesteld zoals hierboven en geeft het een drijvend-kommagetal terug. Merk op dat als u het als een geheel getal wilt krijgen, u het als volgt moet instellen.
exact=True
Het totale aantal duplicaatcombinaties kan ook worden verkregen met het vierde argument, de herhaling. Dit wordt hieronder beschreven.

Nogmaals, merk op dat alleen “import scipy” de speciale module scipy.special niet zal laden.

Zoals in het bovenstaande voorbeeld, voer comb() uit als “from scipy.special import comb” of voer scipy.special.comb() uit als “import scipy.special”. Hetzelfde geldt voor “scipy.misc”.

Hoe math.factorial() niet te gebruiken

Een andere methode die alleen de standaardbibliotheek gebruikt en sneller is dan de methode met math.factorial() is de volgende methode.

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

Genereren en opsommen van combinaties uit lijsten: itertools.combinations()

Het is mogelijk om alle combinaties van lijsten (arrays), enz. te genereren en op te sommen, evenals totale aantallen.

Gebruik de functie combinaties() van de module itertools.

Als je een iterabel (lijst of set) als eerste argument en het aantal te selecteren stukken als tweede argument doorgeeft, krijg je de iterator voor die combinatie.

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

Bereken het totaal aantal duplicaatcombinaties

Het aantal duplo-combinaties is het aantal gevallen waarin r wordt gekozen uit n verschillende combinaties, waarbij doublures zijn toegestaan.

Het totale aantal duplicaatcombinaties is gelijk aan het aantal te kiezen combinaties (r) uit (n + r – 1) verschillende.

Daarom kunnen we de hierboven gedefinieerde functie gebruiken om het totaal aantal combinaties te berekenen.

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

print(combinations_with_replacement_count(4, 2))
# 10

In “scipy.special.comb()”, zoals hierboven beschreven, kan het totale aantal duplicaatcombinaties worden verkregen door het vierde argument “herhaling=True” in te stellen.
Merk op dat het argument “herhaling” niet geïmplementeerd is in “scipy.misc.comb()” in versies ouder dan “SciPy0.14.0”.

from scipy.special import comb

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

Duplicaatcombinaties uit een lijst genereren en opsommen: itertools.combinations_with_replacement()

Het is mogelijk om alle dubbele combinaties van lijsten (arrays), enz. te genereren en op te sommen, evenals totale aantallen.

Gebruik de functie combinaties_met_vervanging() in de module itertools.

Als je een iterabel (lijst of reeks) als eerste argument en het aantal te selecteren stukken als tweede argument doorgeeft, krijg je een iterator voor die overlappende combinatie.

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

Maak anagrammen van strings

Itertools.permutations() maakt het gemakkelijk om string permutaties (anagrammen) te maken.

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

Om een tuple van één karakter per keer te combineren tot een string en er een lijst van te maken, doe je het volgende

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

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

De methode join(), die elementen van een lijst of tupel samenvoegt tot een string, en de notatie list comprehension worden gebruikt.