La funzione di partizione dei numeri interi in Python

La partizione dei numeri interi è un argomento matematico particolarmente complesso da gestire.

Cos'è la partizione dei numeri interi? Consiste nel cercare le possibili somme di un numero intero. Dato un numero n, questo può essere ripartito in k parti. Ad esempio, il numero 3 può essere ottenuto sommando k=3 parti ( 1+1+1 ), in k=2 parti ( 2+1 ) e in k=1 parti ( 3 ). L'ordine dei numeri non conta. Quindi, 2+1 e 1+2 sono la stessa cosa.

Malgrado sia apparentemente un problema semplice da capire, non è altrettanto facile trovare una regola alla serie disordinata di numeri che ne consegue.

La partizione dei numeri interi è uno degli argomenti che i matematici ritengono interessanti. E il più delle volte lo fanno studiare anche agli ingegneri...

Il programma in Python

Programma 1

Per calcolare il numero di volte che il numero può essere ottenuto sommando k parti, ho implementato un noto algoritmo in una funzione ricorsiva del linguaggio python.

Sviluppo la funzione part()

1. def part(n,k,c=0):
2. if (k==n):
3. c+=1
4. if (n>2):
5. if (k==1):
6. c+=1
7. if (n>1):
8. if (k==(n-1)):
9. c+=1
10. if ((k>1)&((n-k)>1)):
11. c=part(n-1,k-1,c)+part(n-k,k,c)
12. return c

Questa funzione calcola le k partizioni di qualsiasi numero intero.

Funziona... ma ha complessità esponenziale.

E' quindi utile per calcolare le partizioni di numeri interi molto bassi.

Per stampare le partizioni fino a dieci aggiungo un ciclo che richiama la funzione passandogli ogni volta un numero intero diverso da 1 a 9.

1. for n in range(1,10):
2. print(n,"|", end=" ");
3. for k in range(1,n+1):
4. c=part(n,k,0)
5. print(c, end=" ")
6. print("")

Il programma stampa in output il triangolo delle partizioni.

Ogni riga indica un numero intero mentre ogni colonna il numero delle k-partizioni.

Ad esempio, la terza colonna indica il numero di partizioni possibili in k=3 parti di ciascun numero.

1 | 1
2 | 1 1
3 | 1 1 1
4 | 1 2 1 1
5 | 1 2 2 1 1
6 | 1 3 3 2 1 1
7 | 1 3 4 3 2 1 1
8 | 1 4 5 5 3 2 1 1
9 | 1 4 7 6 5 3 2 1 1

Posso chiamare la funzione part() anche su singoli numeri e singole partizioni.

Mi basta lanciare una singola istanza.

>>> part(n=6,k=2)
3

Nel precedente esempio la funzione restituisce il numero delle partizioni del numero intero n=6 in k=2 parti.

Il numero 6 può essere ottenuto sommando due parti in 3 singoli casi

5+1
4+2
3+3

E così via.

Programma 2

Questo script invece usa le matrici di numpy.

1. p = np.zeros((20,20), dtype=int)
2. for n in range(1,10):
3. print("")
4. for k in range(1,n+1):
5. if (k==1): p[n,k]=1
6. if (k==n): p[n,k]=1
7. if (n>2):
8. p[n,k]=p[n-1,k-1]+p[n-k,k]
9. print(p[n,k], end=" ")

Fa la stessa cosa.

E' un po' più rapido ma occupa più memoria.

1
1 1
1 1 1
1 2 1 1
1 2 2 1 1
1 3 3 2 1 1
1 3 4 3 2 1 1
1 4 5 5 3 2 1 1
1 4 7 6 5 3 2 1 1
1 5 8 9 7 5 3 2 1 1
1 5 10 11 10 7 5 3 2 1 1
1 6 12 15 13 11 7 5 3 2 1 1
1 6 14 18 18 14 11 7 5 3 2 1 1
1 7 16 23 23 20 15 11 7 5 3 2 1 1
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1

Una volta creata la matrice posso consultarla senza dover ricalcolare i valori ogni volta.

E così via.