Printable View
Un mio amico tempo fa mi ha chiesto se potevo fargli un programma che creasse degli anagrammi. Io ho accettato perché pensavo fosse estremamente facile, ma in realtà sono bloccato.
Ho diviso la stringa data in input in un array di caratteri e ho trovato il numero di possibili combinazioni per ogni stringa. Il problema è però trovare tutte le possibili combinazioni. Qualcuno sa suggerirmi qualcosa? Va bene in qualsiasi (o quasi) linguaggio.
Se devi calcolare quanti anagrammi puoi comporre con una parola di X caratteri, il calcolo è semplice, ti faccio un esempio.
Con la parola ROMA puoi comporre 24 anagrammi, 24 vien fuori usando le permutazioni:
P4 (4 è un pedice) = 4*3*2*1 = 24
24 non è altro che il fattoriale di 4 :wink:
Una funzioncina semplice ma efficace per calcolare il fattoriale con PHP potrebbe essere:
Bye.Codice PHP:<?
function fattoriale($numero){
if($numero <= 1){
return 1; // abbandona la ricorsione
}else{
return $numero*fattoriale($numero-1); //la funzione richiama se stessa
}
}
?>
Ah, la cara vecchia ricorsione... Mi sa che anche il metodo per creare tutti gli anagrammi possibili ti converrà farlo ricorsivo, se non vuoi complicarti troppo la vita. ;-)
Il numero per trovare il numero di combinazioni, come già scritto nel primo messaggio, l'ho già trovato (è simile al tuo ma se ci sono lettere doppie il numero diminuisce).
Il mio problema è trovare tutte le possibili combinazioni. Per esempio: se la parola è "ABC", so già che le possibili combinazioni sono 6, ma non so che sono "ABC", "ACB", "BAC", "BCA", "CAB" e "CBA".
Questo è scritto in Java:E' un po' improvvisato, quindi non ti garantisco che funzioni... di sicuro, però, in caso di caratteri duplicati troverai ripetizioni di palindromi...Codice:public String[] palyndromes (String word)
{
if (word.length () == 0)
return new String[0];
String[] result = new String[factorial (word.length ())];
String front = "", rear = word;
char ch;
int i = 0;
while (front.length () != word.length ())
{
ch = rear.charAt (i);
rear = rear.substring (1);
String[] support = new String[rear.length ()];
support = palyndromes (front + rear);
for (int j = 0; j < support.length; j++)
result[i * support.length + j] = ch + support[j];
front = front + ch;
}
return result;
}
private int factorial (n) { int fact = 1; for (int i = 0; i < n; i++) fact *= i; return fact; }
Ah, avrai capito che i possibili anagrammi di una stringa di n caratteri sono esattamente n! (salvo ripetizioni)... quindi non ti sorprendere se insorgono problemi di memoria quando lavori anche con stringhe piuttosto piccole (anche solo 7-8 caratteri)...
Stammi bene...