Beregne og generere faktorialer, permutationer og kombinationer i Python

Forretning

Standardmodulet math til matematiske funktioner i Python kan bruges til at beregne faktorialer. SciPy har også funktioner til at beregne det samlede antal permutationer\kombinationer.

Modulet itertools kan også bruges til at generere permutationer og kombinationer fra lister (arrays) osv. og til at opregne dem.

Følgende forklares her sammen med en kodeeksempel.

  • faktoriel:math.factorial()
  • Beregn det samlede antal permutationer
    • math.factorial()
    • scipy.special.perm()
  • Generering og opregning af permutationer fra en liste:itertools.permutations()
  • Beregn det samlede antal kombinationer
    • math.factorial()
    • scipy.special.comb()
    • Hvordan man ikke skal bruge math.factorial()
  • Generering og opregning af kombinationer fra lister:itertools.combinations()
  • Beregn det samlede antal dubletkombinationer
  • Generer og opregner duplikerede kombinationer fra en liste:itertools.combinations_with_replacement()

Som et eksempel på anvendelse af permutationer forklares også følgende.

  • Oprette anagrammer fra strenge

Hvis du ønsker at generere en kombination af elementer fra flere lister i stedet for en enkelt liste, skal du bruge itertools.product() i itertools-modulet.

faktoriel: math.factorial()

Matematikmodulet indeholder en funktion factorial(), der returnerer faktorialen.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Negative værdier, der ikke er hele tal, vil resultere i en ValueError.

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

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

Beregn det samlede antal permutationer

math.factorial()

Permutationer er antallet af tilfælde, hvor r vælges blandt n forskellige og placeres i en række.

Det samlede antal permutationer, p, fås ved hjælp af følgende ligning ved hjælp af faktorialer.

p = n! / (n - r)!

Den kan beregnes på følgende måde ved hjælp af funktionen math.factorial(), som returnerer faktorialen. Operatoren ⌘, som udfører heltalsdivision, bruges til at returnere en heltalstype.

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 indeholder en funktion scipy.special.perm(), der returnerer det samlede antal permutationer. Der kræves en separat SciPy-installation. Tilgængelig fra version 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
Det tredje argument er som standard indstillet som ovenfor og returnerer et flydende tal. Bemærk, at hvis du ønsker at få det som et heltal, skal du indstille det som følger.
exact=True

Bemærk, at kun “import scipy” ikke indlæser scipy.special-modulet.

Udfør perm() som “from scipy.special import perm” som i ovenstående eksempel, eller udfør scipy.special.perm() som “import scipy.special”.

Generering og opregning af permutationer fra en liste: itertools.permutations()

Ikke kun samlede tal, men også permutationer kan genereres og opregnes fra lister (arrays) osv.

Brug funktionen permutations() i itertools-modulet.

Hvis en iterabel (liste- eller sæt-type) overføres som det første argument og antallet af stykker, der skal vælges, som det andet argument, returneres en iterator for den pågældende permutation.

import itertools

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

p = itertools.permutations(l, 2)

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

Hvis du vil opregne dem alle, kan du bruge en for-løkke.

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

Da det er en finite iterator, kan den også konverteres til en listetype med list().

Når antallet af elementer i listen er fundet med len(), kan det bekræftes, at det stemmer overens med det samlede antal permutationer, der er beregnet ud fra faktorial.

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

Hvis det andet argument udelades, returneres permutationen til udvælgelse af alle elementer.

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

I itertools.permutations() behandles elementer baseret på position, ikke på værdi. Der tages ikke hensyn til duplikerede værdier.

l = ['a', 'a']

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

Det samme gælder for de følgende funktioner, der er beskrevet nedenfor.

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

Beregn det samlede antal kombinationer

math.factorial()

Antallet af kombinationer er antallet af r brikker, der kan vælges blandt n forskellige brikker. Der tages ikke hensyn til rækkefølgen som i permutationer.

Det samlede antal kombinationer c fås ved hjælp af følgende ligning.

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

Den kan beregnes på følgende måde ved hjælp af funktionen math.factorial(), som returnerer faktorialen. Operatoren ⌘, som udfører heltalsdivision, bruges til at returnere en heltalstype.

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 indeholder en funktion scipy.special.comb(), der returnerer det samlede antal permutationer. Der kræves en separat SciPy-installation. Tilgængelig fra version 0.14.0. Bemærk, at scipy.misc.comb() ikke implementerer den nedenfor beskrevne gentagelse af argumenter.

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
Ligesom med scipy.special.perm() er det tredje argument som standard indstillet som ovenfor og returnerer et glidende tal. Bemærk, at hvis du ønsker at få det som et heltal, skal du indstille det som følger.
exact=True
Det samlede antal duplikerede kombinationer kan også fås med det fjerde argument, gentagelse. Dette er beskrevet nedenfor.

Bemærk igen, at kun “import scipy” ikke indlæser scipy.special-modulet.

Som i ovenstående eksempel skal du udføre comb() som “from scipy.special import comb” eller udføre scipy.special.comb() som “import scipy.special”. Det samme gælder for “scipy.misc”.

Hvordan man ikke skal bruge math.factorial()

En anden metode, der kun bruger standardbiblioteket og er hurtigere end den metode, der bruger math.factorial(), er følgende metode.

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

Generering og opregning af kombinationer fra lister: itertools.combinations()

Det er muligt at generere og opregne alle kombinationer fra lister (arrays) osv. samt samlede tal.

Brug funktionen combinations() i itertools-modulet.

Hvis en iterabel (liste- eller sæt-type) overføres som det første argument og antallet af stykker, der skal vælges, som det andet argument, returneres iteratoren for denne kombination.

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

Beregn det samlede antal dubletkombinationer

Antallet af dubletkombinationer er antallet af tilfælde, hvor r vælges blandt n forskellige kombinationer, idet der tages højde for dubletter.

Det samlede antal duplikerede kombinationer er lig med antallet af kombinationer, der skal vælges (r) ud af (n + r – 1) forskellige kombinationer.

Derfor kan vi bruge den ovenfor definerede funktion til at beregne det samlede antal kombinationer.

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

print(combinations_with_replacement_count(4, 2))
# 10

I “scipy.special.comb()”, der er beskrevet ovenfor, kan det samlede antal dobbeltkombinationer fås ved at indstille det fjerde argument “repetition=True”.
Bemærk, at argumentet “repetition” ikke er implementeret i “scipy.misc.comb()” i versioner forud for “SciPy0.14.0”.

from scipy.special import comb

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

Generer og opregner duplikerede kombinationer fra en liste: itertools.combinations_with_replacement()

Det er muligt at generere og opregne alle duplikerede kombinationer fra lister (arrays) osv. samt det samlede antal.

Brug funktionen combinations_with_replacement() i itertools-modulet.

Hvis en iterabel (liste- eller sæt-type) overføres som det første argument og antallet af stykker, der skal vælges, som det andet argument, returneres en iterator for denne overlappende kombination.

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

Oprette anagrammer fra strenge

Itertools.permutations() gør det nemt at oprette permutationer af strenge (anagrammer).

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

Hvis du vil kombinere en tupel med ét tegn ad gangen til en streng og lave den om til en liste, skal du gøre følgende

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

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

Metoden join(), som sammenkæder elementerne i en liste eller tupel til en streng, og list comprehension notation anvendes.

Copied title and URL