Calcolare e generare fattoriali, permutazioni e combinazioni in Python

Attività commerciale

Il modulo standard math per le funzioni matematiche in Python può essere usato per calcolare i fattoriali. SciPy ha anche funzioni per calcolare il numero totale di permutazioni/combinazioni.

Il modulo itertools può anche essere usato per generare permutazioni e combinazioni da liste (array), ecc. ed enumerarle.

Ciò che segue è spiegato qui, insieme al codice di esempio.

  • fattoriale:math.factorial()
  • Calcolare il numero totale di permutazioni
    • math.factorial()
    • scipy.special.perm()
  • Generare ed enumerare le permutazioni da una lista:itertools.permutations()
  • Calcolare il numero totale di combinazioni
    • math.factorial()
    • scipy.special.comb()
    • Come non usare math.factorial()
  • Generare ed enumerare combinazioni da liste:itertools.combinations()
  • Calcola il numero totale di combinazioni duplicate
  • Genera ed enumera le combinazioni di duplicati da una lista:itertools.combinations_with_replacement()

Come esempio di utilizzo delle permutazioni, si spiega anche quanto segue.

  • Creare anagrammi da stringhe

Se volete generare una combinazione di elementi di più elenchi invece di un singolo elenco, usate itertools.product() nel modulo itertools.

fattoriale: math.factorial()

Il modulo matematico fornisce una funzione factorial() che restituisce il fattoriale.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

I valori non interi e negativi risulteranno in un ValueError.

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

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

Calcolare il numero totale di permutazioni

math.factorial()

Le permutazioni sono il numero di casi in cui r sono scelti tra n diversi e messi in fila.

Il numero totale di permutazioni, p, si ottiene con la seguente equazione usando i fattoriali.

p = n! / (n - r)!

Può essere calcolato come segue utilizzando la funzione math.factorial(), che restituisce il fattoriale. L'operatore ⌘, che esegue la divisione di interi, è usato per restituire un tipo intero.

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 fornisce una funzione scipy.special.perm() che restituisce il numero totale di permutazioni. È richiesta un'installazione separata di SciPy. Disponibile dalla versione 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
Il terzo argomento è impostato di default come sopra e restituisce un numero in virgola mobile. Notate che se volete ottenerlo come un intero, dovete impostarlo come segue.
exact=True

Notate che solo “import scipy” non caricherà il modulo scipy.special.

Eseguire perm() come “from scipy.special import perm” come nell'esempio precedente, o eseguire scipy.special.perm() come “import scipy.special”.

Generare ed enumerare le permutazioni da una lista: itertools.permutations()

Non solo i numeri totali, ma anche le permutazioni possono essere generate ed enumerate da liste (array), ecc.

Usate la funzione permutations() del modulo itertools.

Passando un iterabile (tipo lista o set) come primo argomento e il numero di pezzi da selezionare come secondo argomento, restituisce un iteratore per quella permutazione.

import itertools

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

p = itertools.permutations(l, 2)

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

Per enumerarli tutti, potete usare un ciclo 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')

Poiché è un iteratore finito, può anche essere convertito in un tipo di lista con list().

Quando il numero di elementi nella lista è ottenuto con len(), si può confermare che corrisponde al numero totale di permutazioni calcolato dal fattoriale.

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

Se il secondo argomento è omesso, viene restituita la permutazione per selezionare tutti gli elementi.

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(), gli elementi sono trattati in base alla posizione, non al valore. I valori duplicati non sono presi in considerazione.

l = ['a', 'a']

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

Lo stesso vale per le seguenti funzioni, descritte di seguito.

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

Calcolare il numero totale di combinazioni

math.factorial()

Il numero di combinazioni è il numero di pezzi r da scegliere tra n pezzi diversi. L'ordine non è considerato come nelle permutazioni.

Il numero totale di combinazioni c si ottiene con la seguente equazione.

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

Può essere calcolato come segue utilizzando la funzione math.factorial(), che restituisce il fattoriale. L'operatore ⌘, che esegue la divisione di interi, è usato per restituire un tipo intero.

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 fornisce una funzione scipy.special.comb() che restituisce il numero totale di permutazioni. È richiesta un'installazione separata di SciPy. Disponibile dalla versione 0.14.0. Si noti che scipy.misc.comb() non implementa la ripetizione degli argomenti descritta di seguito.

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
Come con scipy.special.perm(), il terzo argomento è impostato come sopra per default e restituisce un numero in virgola mobile. Notate che se volete ottenerlo come un intero, dovete impostarlo come segue.
exact=True
Il numero totale di combinazioni duplicate può anche essere ottenuto con il quarto argomento, la ripetizione. Questo è descritto di seguito.

Di nuovo, notate che solo “import scipy” non caricherà il modulo scipy.special.

Come nell'esempio precedente, eseguite comb() come “from scipy.special import comb” o eseguite scipy.special.comb() come “import scipy.special”. Lo stesso vale per “scipy.misc”.

Come non usare math.factorial()

Un altro metodo che usa solo la libreria standard ed è più veloce del metodo che usa math.factorial() è il seguente.

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

Generare ed enumerare combinazioni da liste: itertools.combinations()

È possibile generare ed enumerare tutte le combinazioni da liste (array), ecc. così come i numeri totali.

Usate la funzione combinations() del modulo itertools.

Passando un iterabile (tipo lista o set) come primo argomento e il numero di pezzi da selezionare come secondo argomento, restituisce l'iteratore per quella combinazione.

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

Calcola il numero totale di combinazioni duplicate

Il numero di combinazioni duplicate è il numero di casi in cui r viene scelto tra n diversi, tenendo conto dei duplicati.

Il numero totale di combinazioni duplicate è uguale al numero di combinazioni da scegliere (r) tra (n + r – 1) diverse.

Quindi, possiamo usare la funzione definita sopra per calcolare il numero totale di combinazioni.

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()” descritto sopra, il numero totale di combinazioni duplicate può essere ottenuto impostando il quarto argomento “repetition=True.
Si noti che l'argomento “repetition” non è implementato in “scipy.misc.comb()” nelle versioni precedenti a “SciPy0.14.0”.

from scipy.special import comb
print(comb(4, 2, exact=True, repetition=True))
# 10

Genera ed enumera le combinazioni di duplicati da una lista: itertools.combinations_with_replacement()

È possibile generare ed enumerare tutte le combinazioni duplicate da liste (matrici), ecc. nonché i numeri totali.

Usate la funzione combinations_with_replacement() nel modulo itertools.

Passando un iterabile (tipo lista o set) come primo argomento e il numero di pezzi da selezionare come secondo argomento, restituisce un iteratore per quella combinazione sovrapposta.

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

Creare anagrammi da stringhe

Itertools.permutations() rende facile creare permutazioni di stringhe (anagrammi).

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

Per combinare una tupla di un carattere alla volta in una stringa e renderla una lista, fate come segue

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

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

Il metodo join(), che concatena gli elementi di una lista o tupla in una stringa, e la notazione di comprensione della lista sono utilizzati.

Copied title and URL