Il "magico mondo degli anagrammi"

Calcolo Combinatorio ]  [ In PHP ]  [ In Java ]  [ In Prolog ]  [ Un approccio più serio ]

Cinquecento anni fa, il capo di un esagono superiore trovò un libro tanto confuso come gli altri, ma in cui v'erano quasi due pagine di scrittura omogenea, verosimilmente leggibile.
[...]
Si decifrò anche il contenuto; nozioni di analisi combinatoria, illustrate con esempi di permutazioni a ripetizione illimitata. Questi esempi permisero a un bibliotecario di genio di scoprire la legge fondamentale della Biblioteca. Questo pensatore osservò che tutti i libri, per diversi che fossero, constavano di elementi eguali: lo spazio, il punto, la virgola, le ventidue lettere dell'alfabeto. Stabilì inoltre, un fatto che tutti i viaggiatori hanno confermato: non vi sono, nella vasta Biblioteca, due soli libri identici. Da queste premesse incontrovertibili dedusse che la Biblioteca è totale, e che i suoi scaffali registrano tutte le possibili combinazioni dei venticinque simboli ortografici (numero, anche se vastissimo, non infinito) cioè tutto ciò ch'è dato d'esprimere, in tutte le lingue.

Jorge Luis Borges, La Biblioteca di Babele

Un po' di calcolo combinatorio

Quanti sono gli anagrammi di un nome di lunghezza n?
La risposta a questa domanda è abbastanza semplice. Supponiamo per ora che la parola considerata sia formata da tutte lettere diverse.
Ad esempio se consideriamo una parola di lunghezza quattro, CANE, possiamo scegliere di mettere al primo posto una qualsiasi delle quattro lettere (quindi abbiamo 4 possibilità per il primo posto). Per il secondo posto avremo solo 3 possibilità perché una lettera è stata usata, per il terzo le possibilità sono due, per l'ultima posizione la scelta è è obbligata: se abbiamo scritto ACN dobbiamo per forza finire la parola con E (ho scoperto in questo momento che acne è un anagramma di cane). Quindi abbiamo 4 *3 *2 *1 = 24 possibili anagrammi di CANE:

E N A C , N E A C , E A N C , A E N C , N A E C , A N E C , E N C A , N E C A , E C N A , C E N A , N C E A , C N E A , E A C N , A E C N , E C A N , C E A N , A C E N , C A E N , N A C E , A N C E , N C A E , C N A E , A C N E , C A N E.

Questa regola è vera in generale. Se una parola contiene n simboli senza ripetizioni, il numero dei suoi anagrammi, cioè il numero delle permutazioni di n oggetti è n fattoriale, cioè

n ! = n (n-1) (n-2) ... 1

Il fattoriale è una funzione che cresce MOLTO velocemente, come si può vedere dalla seguente tabella

n n!
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
n n!
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000

Consideriamo il caso in cui ci siano delle lettere che compaiono più volte. Allora non vogliamo contare due volte ad esempio la parola KOALA distinguendo le due possibili posizioni delle due A. Quindi dobbiamo dividere il numero totale delle permutazioni per il numero di tutte le permutazioni possibili dei simboli che si ripetono. Ad esempio nel conteggio originale la parola AMACA verrebbe contata 6 volte, tante quante sono le possibili permutazioni delle tre A. La parola BAOBAB verrebbe contata 12 volte, cioè il prodotto delle permutazioni possibili delle tre A (6) e delle due B (2).
In generale i possibili anagrammi di una parola che contiene n simboli di cui uno si ripete s1 volte, un altro s2 volte, e un k-esimo si ripete sk volte sono

n ! / (s1! s2! .... sk!)

Nel caso limite che i simboli siano tutti uguali (la parola AAAAAAA), la formula dà il risultato corretto cioè n!/n!=1

Per esempio i possibili anagrammi di LORENZO MASETTI, cioè di 14 simboli tra i quali però la O, la E e la T si ripetono due volte, sono

14!/ (2! * 2! * 2!) = 10897286400

Tra tutti questi anagrammi ce ne saranno un'infinità senza senso, ma alcuni veramente fantastici... La Letizia che è appassionata di queste cose me ne segnala tantissimi, i più belli sono IN SETT' ORE M' ALZO, ZONA TRE MESTOLI, O MATTO SENZA LIRE, TRL, SENZA TE MOIO, poi quello erotico: T' ALZO I SENI, TREMO (da chiedersi cosa ci tenesse lei sotto i seni!) e quello volgare, TEMEA IL STRONZO.

A questo punto se ti interessa l'algoritmo per trovare le permutazioni vai alla sezione prolog, se no continua...

Il programma in PHP

Ecco finalmente il programma che fa gli anagrammi. In realtà questo programma non tiene conto di quanto appena detto cioè delle lettere che si ripetono, infatti calcola tutte le permutazioni della parola.
L'algoritmo utilizza una procedura ricorsiva. Come caso base considera le permutazioni di due oggetti, che sono facili da calcolare (AB e BA). Per più di due oggetti sfrutta la proprietà che per calcolare le permutazioni di n oggetti basta mettere in testa ognuno degli n elementi e farlo seguire da tutte le possibili permutazioni dei restanti n-1 oggetti.

Il programma è scritto in PHP, un potente linguaggio di script per il web che viene interpretato dal server prima di essere spedito al computer client, cioè a te che stai leggendo questa pagina. Per questo ho dovuto limitare il numero di caratteri della parola da anagrammare a 8, infatti una regola del php è che il tempo di esecuzione sul server non può superare i 30 secondi, e questo tempo non sarebbe sufficiente a calcolare tutti i 362880 anagrammi di una parola di 9 lettere.

Questo programma scrive tutti gli anagrammi di una qualsiasi parola lunga al massimo 8 caratteri.
Gli spazi non contano.

Testo:


   
Sorgente PHP

Il Programma in Java

Ho scritto anche una applet java che realizza esattamente lo stesso algoritmo dello script php per scrivere tutti gli anagrammi. Visto che le applet sono eseguite sul vostro computer, non c'è nessuna limitazione alla lunghezza della parola. Tenete presente però che aumentando la lunghezza, il tempo di esecuzione aumenta a dismisura!

L'applet in funzione

In prolog... con otto istruzioni!

Questo genere di programmi si realizzano molto bene con la programmazione logica.
In prolog è molto facile scrivere gli algoritmi proprio come si pensano. Roba da matematici... ma affascinante!
Come abbiamo visto il problema di trovare gli anagrammi è equivalente a quello di trovare le permutazioni di una lista. L'algoritmo per trovare tutte le permutazioni si basa su questa idea:

  • (caso base) Le permutazioni della lista vuota sono solo la lista vuota.

  • (caso ricorsivo) Le permutazioni di una lista non vuota sono date da tutte le liste così composte: in testa hanno un elemento qualsiasi della lista di partenza seguito da tutte le possibili permutazioni della lista composta dagli elementi restanti.

Questo algoritmo si scrive in prolog in quattro righe. L'ho copiato (scandalosamente) dal prof. Aguzzi! Vengono definite due relazioni: permutation che mette in relazioni due liste di cui una è una permutazione dell'altra, e select che è la relazione tra un elemento di una lista, la lista da cui l'elemento è estratto e la lista degli elementi che restano nella lista se si leva quell'elemento (ad esempio valgono le relazioni select(1,[1, 2], [2]) e select (2,[1, 2],[1])).

permutation([],[]).
permutation([X | Xs],[Z | Zs]) :- select(Z,[X | Xs],Ys),permutation(Ys,Zs).

select(X,[X | Xs],Xs).
select(Y,[X | Xs],[X | Ys]) :- select(Y,Xs,Ys).

Il significato delle quattro istruzioni è questo:

  1. Le permutazioni di una lista vuota sono date dalla sola lista vuota.

  2. Le permutazioni di una lista non vuota (che si rappresenta con [X | Xs] che significa la lista che inizia con l'elemento X e continua con la lista Xs, che può eventualmente anche essere vuota) sono date dalla lista [Z | Zs] a patto che Z sia un elemento selezionato da [X | Xs] e Ys sia la lista degli elementi restanti in [X | Xs] quando si toglie Z, e Zs sia una permutazione di Xs.

  3. Il caso più semplice: X � il primo elemento della lista [X | Xs] e quello che resta è la coda Xs

  4. La chiamata ricorsiva: l'elemento X non viene selezionato ma viene messo in testa alla lista degli elementi restanti. La select viene richiamata ricorsivamente sulla coda.

La forza del prolog sta nel backtracking che permette di adottare una tecnica di programmazione non deterministica.
Aggiungendo altre quattro righe si ottiene il programma prolog di cui riporto una tipica esecuzione:

?- anagrammi('punk').
punk
pukn
pnuk
pnku
pkun
pknu
upnk
upkn
unpk
unkp
ukpn
uknp
npuk
npku
nupk
nukp
nkpu
nkup
kpun
kpnu
kupn
kunp
knpu
knup
 
Yes

Se ti interessa usare il prolog puoi scaricarne un'ottima versione, lo swi-prolog all'indirizzo http://www.swi-prolog.org.

Un approccio diverso (e più serio)

Se poi volete un programma un po' più serio per costruire anagrammi sensati potete visitare...

Il motore anagrammatico del GAUNT



"Guarda!" gridò la vocetta petulante della scimmia, e con le sue manine lo costrinse a voltar la testa in un'altra direzione. "Guarda laggiù! Non è divertente? Là c'era un gruppo di gente, uomini e donne, vecchi e giovani, tutti negli abbigliamenti più stravaganti, tutti zitti e intenti, ciascuno per proprio conto, a mescolare e a gettare un'enorme quantità di dadi. Su ciascuna faccia di ogni dado c'era una lettera dell'alfabeto. Mescolavano i dadi e poi restavano immobili a fissarli.
"Che cosa fanno?" sussurrò Bastian. "Che gioco è? Come si chiama?"
"Il gioco del Caso", rispose Argax. Fece un cenno ai giocatori e gridò: "Bravi, ragazzi miei, su, su, coraggio! Avanti così! Mai smettere!" Poi si volse a Bastian e gli mormorò all'orecchio: "Non possono più raccontare niente. Hanno perduto la parola. Perciò ho studiato per loro questo gioco. Come vedi, li tiene occupati. Ed è anche molto semplice. se ci pensi bene, ti avvedi subito che tutte le storie del mondo sono contenute nelle ventisei lettere dell'alfabeto. Le lettere sono sempre le stesse, sono solo le combinazioni che cambiano. E con le stesse lettere si formano parole, con le parole frasi, con le frasi capitoli e con i capitoli le storie. Ecco, guarda lì, che cosa ci sta scritto?"
Bastian lesse:

HGIKLOPFMWEYVXQ
YXCVBNMASDFGHJKLOA
QWERTZUIOPU
ASDFGHJKLOA
MNBVCXYLKJHGFDSA
UPOIUZTREWQAS
QWERTZUIOPUASDF
YXCVBNMLKJ
QWERTZUIOPU
ASDFGHJKLOAYXC
UPOIUZTREWQ
AOLKJHGFDSAMNBV
GKHDSRZIP
QUETUOUSFHKO
YCBMWRZIP
ARCGUNIKYO
QWERTZUIOPUASD
MNBVCXYASD
LKJUONGREFGHL

"Sicuro", rise la scimmia, "il più delle volte è così. Ma quando vai avanti a farlo a lungo, per anni e anni, qualche volta capita anche che salti fuori per puro caso una parola. Non parole molto intelligenti o spiritose ma, insomma, per lo meno parole. Parachiaviccoli, per esempio, o salamedipere, o giradisotto. Ma se vai ancora avanti per cento, mille, centomila anni a fare lo stesso gioco, secondo il più banale calcolo delle probabilità dovrebbe poter venir fuori almeno una poesia. E quando poi lo si fa per l'eternità, in questo modo devono per forza venir fuori tutte le storie, tutte quelle che esistono e che sono praticamente possibili, e con queste anche le storie delle storie e persino questa storia in cui ora stiamo parlando. Logico non ti pare?"
"Ma è spaventoso", disse Bastian.
"Oh", fece Argax, "dipende dal punto di vista. Questi qui, si potrebbe dire, ci si divertono un mondo. E del resto, che altro vuoi che ce ne facciamo di loro in Fantàsia?"

Michael Ende, La storia Infinita

Home