[ 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. Jorge Luis Borges, La Biblioteca di Babele |
Un po' di calcolo combinatorioQuanti sono gli anagrammi di un nome di lunghezza n? 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
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).
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 PHPEcco 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. 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.
Il Programma in JavaHo 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 funzioneIn prolog... con otto istruzioni!Questo genere di programmi si realizzano molto bene con la programmazione logica.
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:
La forza del prolog sta nel backtracking che permette di adottare una tecnica di programmazione non deterministica. ?- 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. 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?" Michael Ende, La storia Infinita |