Visualizza il feed RSS

Titolo provvisorio...

Un problemino con le addizioni... +1

Valutazione: 5 voti, con una media del 5.00.
di pubblicato il 22-03-2010 alle 00:56 (4404 Visite)
Abstract: questo post è alquanto lungo, tanto da dover essere suddiviso su due blog entries. Vale dunque la pena di anticiparne i contenuti in poche righe iniziali. Nella parte precedente si è parlato di partizioni di numeri naturali, cioè dei modi per scrivere un numero dato come somma di altri numeri interi positivi: queste somme finite vengono studiate sistematicamente in matematica da almeno tre secoli, hanno proprietà importanti in Teoria dei Numeri e matematica discreta, e costituiscono inoltre un esercizio di programmazione combinatoria molto valido, sebbene elementare.
In questa seconda parte sono presentati opportuni esempi di algoritmi combinatori implementati nei linguaggi più idonei, e viene replicata la minimale bibliografia introduttiva.


Dopo avere visto la formula di Hardy-Ramanujan-Rademacher per determinare il numero complessivo di partizioni di un naturale n, è forse opportuno un brevissimo excursus, con l'autorevole compagnia del professor Stanley. Cercherò di tradurre e condensare in poche righe l'intera filosofia che è magistralmente riassunta nelle prime pagine del suo capolavoro [16], del quale attualmente è in preparazione una imperdibile seconda edizione.

Quella formula strabiliante, al di là dell'ammirazione e dello stupore, ci trova però anche riluttanti: proviamo a capire il perché.

Stanley porta quattro esempi fondamentali per spiegare meglio cosa si possa realmente considerare una formula soddisfacente, in forma chiusa ed esplicita:

1. L'insieme delle parti (o insieme potenza) di un insieme finito con cardinalità espressa dal naturale n, cioè l'insieme di tutti i possibili sottoinsiemi che si possono formare dall'insieme di partenza, ha un numero totale di elementi dato da:

Formula LaTeX: {\color{blue}\wp(n)\ =\ 2^n}

...e tutti, profani inclusi, sono d'accordo nel considerarla una formula perfettamente soddisfacente !

2. Si supponga che n signori consegnino i loro n cappelli ad una guardarobiera. Sia f(n) il totale dei modi in cui costoro possono riavere indietro quei cappelli, facendo però sì che nessuno riceva il proprio cappello, quello cioè che aveva in testa al suo arrivo.
L'espressione della nostra f(n), in questo caso, è data da:

Formula LaTeX: {\color{blue}f(n)\ =\ n!\,\sum_{k\,=\,0}^{n}\frac{(-1)^k}{k!}}

Tale formula, sebbene marcatamente meno elegante della precedente, è comunque accettabile "in mancanza di una risposta più semplice", anche perché è in grado di semplificare (in un senso ben quantificabile) il calcolo dei valori di f(n). Inoltre, la sua aderenza ad un importante principio (quello detto di inclusione/esclusione) la rende comunque "intuitiva" a chi abbia un minimo di familiarità con la materia.

3. Qui Stanley invita a considerare come f(n) il numero di matrici booleane quadrate nxn tali che ciascuna riga e colonna contiene esattamente tre valori pari a 1. La formula migliore nota ad oggi è:

Formula LaTeX: {\color{blue}f(n)\ =\ \frac{(n!)^2}{6^n}\ \sum\frac{(-1)^\beta(\beta\,+\,3\gamma)!2^\alpha3^\beta}{ \alpha! \beta! (\gamma!)^2\, 6^\gamma}}

Dove la sommatoria copre tutte le soluzioni naturali all'equazione

Formula LaTeX: \\ {\color{blue} \alpha\ +\ \beta\ +\ \gamma\ =\ n \text{, che in totale assommano a }\ \frac{(n\,+\,2)(n\,+\,1)}{2}}

L'unico motivo per accettare (con riluttanza) una simile formula, scrive Stanley, è di natura computazionale - sebbene essa non ci dica quasi alcunché di significativo riguardo alla natura della funzione studiata.

4. Ultimo e peggiore esempio, ci sono in letteratura "funzioni" di conteggio la cui valutazione richiede nulla meno che un'enumerazione esaustiva (o quasi) degli oggetti contati. Una simile "formula" è decisamente priva di valore e poco utile, conclude l'esimio professore.


Con questo, spero vivamente di aver trasmesso almeno un'idea dello spirito della matematica discreta e costruttiva, che si esprime sovente in uno spiccato senso estetico per le formule, con forti valenze anche etiche e pragmatiche.

Giunti a questo punto, ritengo che ci siamo dilungati (e dilettati) a sufficienza. É infatti arrivato il momento delle buone notizie, informaticamente parlando: sfruttando la relazione di ricorrenza già nota a Leonhard Euler e sue semplici derivate, è possibile costruire algoritmi elementari ed accettabilmente efficienti per il calcolo esatto di P(n) e valori correlati, che spazzano via gli incubi e fanno tornare il sorriso ai programmatori, giovani e meno giovani, che si trovino ad affrontare l'argomento.

Dunque, è ora di metter mano al codice!

Direi di iniziare proprio con un bel colpo di maglio che demolisce lo spauracchio del "formulone" calcolando in modo iterativo il numero di partizioni di tutti gli interi compresi tra 0 e il parametro n incluso, usando unicamente operazioni elementari. Totale, una dozzina di LOC in C ben scritte.

Non tentate di utilizzare questo codice, chiaramente didattico, per numeri troppo grandi: al di là dell'ovvio limite nell'array statico P[25], la funzione di partizione cresce in modo esplosivo al crescere di n, con ovvie conseguenze in termini di rappresentabilità hardware. Per andare oltre occorrono apposite librerie, come la nota MIRACL: oppure il sano Python.

codice:
/*
**  IntegerPartitions.c
**  October 1, 1997
**  This program implements Algorithm 3.1 - 3.9
*/

#include <stdio.h>
#include <stdlib.h>

int P[25];

void EnumPartitions2(int m)
/*
**  Algorithm 3.6
**  compute the partition numbers P[i] for i <= m
*/
{
    int i;

    P[0] = 1;
    P[1] = 1;

    for(i = 2; i <= m; ++i)
    {
        int j, k, sum, omega, omega2, sign;

        sign  = 1;
        omega = 1;
        sum   = 0;
        j = 1;
        k = 1;

        while (omega <= i)
        {
            omega2 = omega + j;

            sum += sign * P[i - omega];

            if (omega2 <= i)
            {
                sum += sign * P[i - omega2];
            }

            ++j;
            k += 3;
            omega += k;
            sign = -sign;
        }
        P[i] = sum;
    }
}

int main(void)
{
    int i, n = 22;

    printf("\nTest of Algorithm 3.6 with n = %d \n\n", n);

    EnumPartitions2(n);

    printf("  n  |");
    for( i = 1; i <= n; i = i + 1 )
    {
        printf("%5d", i);
    }

    printf("\n-----|");
    for( i = 1; i <= n; i = i + 1 )
    {
        printf("-----");
    }

    printf("\nP[n] |");
    for( i = 1; i <= n; i = i + 1 )
    {
        printf("%5d", P[i]);
    }

    printf("\n\nEnd of all tests.\n\n");
    return (0);
}
Il codice qui presentato è un semplice riadattamento dell'algoritmo euleriano 3.6 del Kreher-Stinson [07]: il loro sorgente C originale IntegerPartitions.c è contenuto nell'archivio GEN.tar.gz, liberamente scaricabile presso la sezione "source code" della home page di supporto al testo.

In definitiva, comunque, è molto più semplice e lineare di quanto si potesse temere leggendo la formula di Hardy-Ramanujan-Rademacher, nevvero ?

Per ulteriori considerazioni in ordine a questa implementazione, rimando il lettore interessato alla entry appositamente creata. Preferisco dedicare il poco spazio rimanente ad altri argomenti oltre la funzione di partizione, che peraltro troviamo implementata e ottimizzata in tutti i grandi frameworks e librerie per il calcolo numerico e simbolico. Le implementazioni interne dei grandi framework di calcolo fanno quasi sempre uso di algoritmi basati sulla formula di Rademacher modificata, possibilmente applicata solo quando l'input diventa relativamente grande per l'algoritmo euleriano. Ad esempio, citerei volentieri l'ottimo lavoro di Jonathan Bober incluso nel noto ambiente SAGE.

Tutti i vari testi citati contengono numerosi esempi di codice per la generazione esaustiva e vincolata di partizioni (es. partizioni con valore massimo m, ovvero con esattamente m parti). Sono facilmente disponibili ottime ed efficienti soluzioni in C (alcune anche in C++, come quelle proposte da J. Arndt in [03]) dalle quali si può apprendere molto, ma che non posso qui riportare e commentare per le consuete limitazioni di spazio e copyright.

Invito caldamente tutti i miei lettori a familiarizzare con il codice disponibile nelle varie homepages, tutte citate in bibliografia, e ricordo che buona parte dei testi citati è oggi liberamente disponibile per il download presso i siti dei rispettivi autori, a volte con blande limitazioni (del tutto irrilevanti ai fini dello studio individuale).

Parlando di Python, una soluzione ricorsiva piuttosto elegante (sebbene dalle prestazioni limitate, come tutte le implementazioni di tale genere) viene dagli archivi delle "recipes" di Python sul sito ActiveState ed è dovuta a David Eppstein:
codice:
def partitions(n):
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return
        
    # modify partitions of n-1 to form partitions of n
    for p in partitions(n-1):
        yield [1] + p
        if p and (len(p) < 2 or p[1] > p[0]):
            yield [p[0] + 1] + p[1:]
Ma naturalmente le soluzioni più eleganti in assoluto sono quelle offerte dai paradigmi non convenzionali. Ecco una splendida soluzione in J, derivata dall'articolo [04].

codice:
parts=.monad define
(],~ >:@i.@[ <@;@:(([,.(>:{."1)#])&.>) {.)&.>/(<<i.1 0),~<"0(],(](-<.>:@])i.)@<:) y
)
Una volta superata l'impressione che tale apparentemente insensata sequenza di caratteri sia il risultato della pigra passeggiata di un micio sulla tastiera, è facile convincersi - magari anche compulsando con attenzione l'articolo relativo - che si tratta di una delle soluzioni più eleganti in assoluto per la generazione esaustiva di partizioni, peraltro ragionevolmente efficiente.
Ecco uno snapshot dell'output:

codice:
   parts 6
┌────────────────────────────────────────────┐
│┌───────────┬─────────┬───────┬─────┬───┬─┬┐│
││1 1 1 1 1 1│1 1 1 1 1│1 1 1 1│1 1 1│1 1│1│││
││2 1 1 1 1 0│         │2 1 1 0│2 1 0│2 0│ │││
││2 2 1 1 0 0│         │2 2 0 0│3 0 0│   │ │││
││2 2 2 0 0 0│         │       │     │   │ │││
││3 1 1 1 0 0│         │       │     │   │ │││
││3 2 1 0 0 0│         │       │     │   │ │││
││3 3 0 0 0 0│         │       │     │   │ │││
││4 1 1 0 0 0│         │       │     │   │ │││
││4 2 0 0 0 0│         │       │     │   │ │││
││5 1 0 0 0 0│         │       │     │   │ │││
││6 0 0 0 0 0│         │       │     │   │ │││
│└───────────┴─────────┴───────┴─────┴───┴─┴┘│
└────────────────────────────────────────────┘
Fino a qui abbiamo a malapena scalfito la superficie di questo vasto argomento, le cui diramazioni e connessioni con altri gangli vitali della matematica discreta, combinatoria e computazionale sono innumerevoli, e spesso poco predicibili.
La quantità di concetti essenziali omessi è enorme, purtroppo: a cominciare dai multinsiemi, fino alle notazioni estese e ad altre strutture fondamentali della matematica discreta.

Spero comunque, al di là di errori, omissioni, imprecisioni e necessarie superficialità, di aver suscitato interesse, curiosità e voglia di approfondire l'argomento.


Riporto anche qui, per comodità, la nano-bibliografia già proposta.

[01] G. Almkvist & H. S. Wilf, "On the coefficients in the Hardy-Ramanujan-Rademacher formula for p(n)", J. Number Theory 50 (1995), 329—334; {link}

[02] G. E. Andrews, "The theory of partitions", Encyclopedia of Mathematics and Its Applications, Gian-Carlo Rota (editor), Addison-Wesley, 1976

[03] J. Arndt, "Matters Computational", {preprint}

[04] R. E. Boss, "Partitions of numbers: An efficient algorithm in J", Vector, Vol. 23, Issue 4, {link}

[05] R. Kanigel, "L'uomo che vide l'infinito. La vita breve di Srinivasa Ramanujan, genio della matematica", Rizzoli, 2003

[06] D. E. Knuth, "The Art of Computer Programming, Vol. 4", Addison-Wesley, 2004, {link}

[07] D. L. Kreher & D. R. Stinson, "Combinatorial Algorithms: Generation, Enumeration and Search", CRC Press, 1998, {link}

[08] G. H. Hardy & S. Ramanujan "Asymptotic formulae in combinatorial analysis", Proc. London Math. Soc., 17, 237-252 (1918)

[09] E. Munarini e N. Zagaglia Salvi, "Matematica Discreta", UTET Città Studi, 1997

[10] A. Nijenhius & H. S. Wilf, "Combinatorial Algorithms", Academic Press, 1975, {download}

[11] H. Rademacher, “On the Partition Function p(n)”, Proc. London Math. Soc. 43, 241-254, 1937

[12] E. M. Reingold + J. Nievergelt & N. Deo, "Combinatorial Algorithms", Prentice Hall, 1977

[13] F. Ruskey, "Combinatorial Generation", {electronic edition}

[14] M. du Sautoy, "L'enigma dei numeri primi", Rizzoli, 2004

[15] S. S. Skiena, "The Algorithms Design Manual, 2nd ed.", Springer, 1997, {link}

[16] R. Stanley, "Enumerative Combinatorics, Vol. 1", Cambridge University Press, 1997, {link}

[17] E. W. Weisstein, “Partition” - MathWorld, a Wolfram Web Resource, {link}

[18] A. Zoghbi & I. Stojmenovic, "FAST ALGORITHMS FOR GENERATING INTEGER PARTITIONS", Intern. J. Computer Math., Vol- 70. pp. 319-332, {link}

Commenti