Beräkna och generera faktorier, permutationer och kombinationer i Python.

Företag

Standardmodulen math för matematiska funktioner i Python kan användas för att beräkna faktorier. SciPy har också funktioner för att beräkna det totala antalet permutationer\kombinationer.

Modulen itertools kan också användas för att generera permutationer och kombinationer från listor (matriser) etc. och räkna upp dem.

Följande förklaras här, tillsammans med exempelkod.

  • Factorial:math.factorial()
  • Beräkna det totala antalet permutationer
    • math.factorial()
    • scipy.special.perm()
  • Generera och räkna upp permutationer från en lista:itertools.permutations()
  • Beräkna det totala antalet kombinationer
    • math.factorial()
    • scipy.special.comb()
    • Hur man inte använder math.factorial()
  • Generera och räkna upp kombinationer från listor.:itertools.combinations()
  • Beräkna det totala antalet dubbla kombinationer.
  • Generera och räkna upp dubbla kombinationer från en lista:itertools.combinations_with_replacement()

Som ett exempel på användning av permutationer förklaras också följande.

  • Skapa anagram från strängar

Om du vill generera en kombination av element från flera listor i stället för en enda lista använder du itertools.product() i itertools-modulen.

Factorial: math.factorial()

Matematikmodulen har en funktion factorial() som ger faktorn.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Negativa värden som inte är heltal resulterar i ett ValueError.

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

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

Beräkna det totala antalet permutationer

math.factorial()

Permutationer är antalet fall där r väljs från n olika och placeras i en rad.

Det totala antalet permutationer, p, erhålls genom följande ekvation med hjälp av faktornummer.

p = n! / (n - r)!

Den kan beräknas på följande sätt med hjälp av funktionen math.factorial(), som ger faktorn. Operatorn ⌘, som utför heltalsdivision, används för att returnera en heltalstyp.

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 har en funktion scipy.special.perm() som returnerar det totala antalet permutationer. En separat SciPy-installation krävs. Tillgänglig från och med 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 argumentet är som standard inställt som ovan och returnerar ett flyttal. Observera att om du vill få det som ett heltal måste du ställa in det på följande sätt.
exact=True

Observera att endast ”import scipy” inte laddar modulen scipy.special.

Exekvera perm() som ”from scipy.special import perm” som i exemplet ovan, eller exekvera scipy.special.perm() som ”import scipy.special”.

Generera och räkna upp permutationer från en lista: itertools.permutations()

Inte bara totala tal utan även permutationer kan genereras och räknas upp från listor (arrays) osv.

Använd funktionen permutations() i modulen itertools.

Om du skickar en iterabel (av typen lista eller uppsättning) som första argument och antalet bitar som ska väljas som andra argument returneras en iterator för den permutationen.

import itertools

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

p = itertools.permutations(l, 2)

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

För att räkna upp dem alla kan du använda en for-slinga.

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

Eftersom det är en ändlig iterator kan den också konverteras till en listtyp med list().

När antalet element i listan erhålls med len() kan det bekräftas att det stämmer överens med det totala antalet permutationer som beräknats med hjälp av faktorn.

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

Om det andra argumentet utelämnas returneras permutationen för att välja alla element.

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() behandlas element baserat på position, inte värde. Dubbla värden beaktas inte.

l = ['a', 'a']

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

Samma sak gäller för följande funktioner, som beskrivs nedan.

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

Beräkna det totala antalet kombinationer

math.factorial()

Antalet kombinationer är antalet r bitar att välja mellan n olika bitar. Ordningen beaktas inte som i permutationer.

Det totala antalet kombinationer c erhålls genom följande ekvation.

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

Den kan beräknas på följande sätt med hjälp av funktionen math.factorial(), som ger faktorn. Operatorn ⌘, som utför heltalsdivision, används för att returnera en heltalstyp.

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 har en funktion scipy.special.comb() som returnerar det totala antalet permutationer. En separat SciPy-installation krävs. Tillgänglig från och med version 0.14.0. Observera att scipy.misc.comb() inte implementerar den argumentrepetition som beskrivs nedan.

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
Precis som med scipy.special.perm() är det tredje argumentet som standard inställt som ovan och returnerar ett flyttal. Observera att om du vill få det som ett heltal måste du ställa in det på följande sätt.
exact=True
Det totala antalet dubbla kombinationer kan också fås med det fjärde argumentet, upprepning. Detta beskrivs nedan.

Observera återigen att endast ”import scipy” inte laddar scipy.special-modulen.

Som i exemplet ovan, kör comb() som ”from scipy.special import comb” eller kör scipy.special.comb() som ”import scipy.special”. Samma sak gäller för ”scipy.misc”.

Hur man inte använder math.factorial()

En annan metod som endast använder standardbiblioteket och som är snabbare än den som använder math.factorial() är följande metod.

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

Generera och räkna upp kombinationer från listor.: itertools.combinations()

Det är möjligt att generera och räkna upp alla kombinationer från listor (matriser) etc. samt totala antal.

Använd funktionen combinations() i modulen itertools.

Om du skickar en iterabel (av typen lista eller uppsättning) som första argument och antalet bitar som ska väljas som andra argument returneras iteratorn för den kombinationen.

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

Beräkna det totala antalet dubbla kombinationer.

Antalet dubbla kombinationer är antalet fall där r väljs från n olika kombinationer, med hänsyn tagen till dubbla kombinationer.

Det totala antalet dubbla kombinationer är lika med antalet kombinationer att välja (r) av (n + r – 1) olika kombinationer.

Därför kan vi använda den funktion som definieras ovan för att beräkna det totala antalet 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()” som beskrivs ovan kan det totala antalet dubbla kombinationer erhållas genom att ställa in det fjärde argumentet ”repetition=True”.
Observera att argumentet ”repetition” inte är implementerat i ”scipy.misc.comb()” i versioner före ”SciPy0.14.0”.

from scipy.special import comb

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

Generera och räkna upp dubbla kombinationer från en lista: itertools.combinations_with_replacement()

Det är möjligt att generera och räkna upp alla dubblettkombinationer från listor (matriser) etc. samt totala antal.

Använd funktionen combinations_with_replacement() i modulen itertools.

Om du skickar en iterabel (av typen lista eller uppsättning) som första argument och antalet delar som ska väljas som andra argument returneras en iterator för den överlappande kombinationen.

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

Skapa anagram från strängar

Itertools.permutations() gör det enkelt att skapa strängpermutationer (anagram).

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 du vill kombinera en tupel med ett tecken i taget till en sträng och göra den till en lista gör du följande

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

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

Metoden join(), som sammanfogar element i en lista eller tupel till en sträng, och listförståelsen används.