Newsgroup: it.comp.lang.c++
Titolo: AIUTO ESAMI 3 VI PREGO UNA RISPOSTA!!!

Insomma io non voglio sapere l'esatto codice del programma ... voglio solo
sapere come posso creare anagrammi usando gli array ... forse con il rand?
E poi vorrei anche sapere come si creano solo quelli di senso compiuto senza
includere alcun dizionario visto che io tanto non lo so includere ....
AIUTO!
Ciao e Grazie

includere alcun dizionario visto che io tanto non lo so includere ....
Devi chiedere l'algoritmo al Tenente Comandante Data. 8)
Luc.

 wrote:

Le strade migliori percorribili sono quelle che ti sono state esposte
nei messaggi precedenti (vedi la soluzione di Andrea Griffini).
Non e' detto che tu abbia bisogno di *generare* gli anagrammi, hai
solo bisogno di caricare un dizionario di coppie (firma/parola).
Per esempio : la parola "lavagna" ha firma "aaaglnv" (ordine
alfabetico delle lettere), cosi' come "valanga".
Nel dizionario avrai che alla firma "aaaglnv" corrispondono due parole
(valanga e lavagna).
CHIAVE        PAROLE ASSOCIATE
------------------------------
aaaglnv ----> lavagna, valanga  
Data, quindi, la parola "valanga", non ti serve *calcolare* gli
anagrammi, ma solo la sua firma, andare a spulciare il dizionario
(usando la firma come chiave) e vedere quali sono le parole associate
ad essa (in questo caso troveresti "lavagna").
Se invece cio' che ti interessa e' realmente la generazione degli
anagrammi, ti dico come farei io.
Gli anagrammi si creano molto facilmente per via ricorsiva.
Ad esempio, volendo anagrammare ROMA, si procede nel modo seguente :
R + gli anagrammi di OMA
    O + gli anagrammi di MA      
        M + gli anagrammi di A   
        A + gli anagrammi di M
    M + gli anagrammi di OA     
        O + gli anagrammi di A
        A + gli anagrammi di O
    A + gli anagrammi di OM
        O + gli anagrammi di M
        M + gli anagrammi di O
O + gli anagrammi di RMA
    ...
M + gli anagrammi di ROA
    ...
A + gli anagrammi di ROM
    ...
A questo punto, il dizionario devi comunque caricarlo (puoi usare lo
stesso principio di prima). In questo caso, pero', scarterai tutte
quelle parole che non costituiscono una firma per il dizionario.
Il codice seguente l'ho scritto in mezz'ora e di fretta, quindi non
badare all'efficienza, ma alla leggibilita'...
<CODE>
#include <iostream>
#include <string>
using namespace std ;
string estratto( string s, int idx )
{
       return s.substr( 0, idx ) + s.substr( idx + 1 ) ;
}
void anagramma( string radice, string s, int livello )
{
     for ( int i = 0 ; i < s.size() ; i++ )
     {
         string t = radice + s[i] ;
         if ( t.size() == livello )
         {
            cout << t << endl ;
         }
         anagramma( t, estratto( s, i ), livello ) ;
     }
}
void calcola_anagrammi( string s )
{
     anagramma( "", s, s.size() ) ;
     // c'e' sicuramente un modo per ottimizzare questo
     // doppio passaggio...
}
int main()
{
    string my_string ;
    cout << "Inserire la stringa da anagrammare : " ;
    cin  >> my_string ;
    calcola_anagrammi( my_string ) ;
    return 0 ;
}
</CODE>
--
Andrea Laforgia (ICQ 87230455)
http://www.geocities.com/AndreaLaforgia
"ci sono tre tipi di persone nel mondo : quelli che
 sono bravi in matematica e quelli che non lo sono."

 includere alcun dizionario visto che io tanto non lo so includere ....
Se non includi un dizionario per fare i confronti, è materialmente
impossibile che il tuo programma possa riconoscere il concetto di "senso
compiuto", a meno che non implementi qualche routine di intelligenza
artificiale ;-)
Massimo

non lo so includere ....
Hmmm... questo non credo che sia facilissimo. Ad esempio per te
"brachistocrona" e' una parola di senso compiuto ?
Senso compiuto dipende dal vocabolario che si conosce...
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 wrote:


Eh si sigh .... :-( io del codice di Andrea Laforgia (che tra le altre cose
ringrazio tantissimo) non ho capito alcune le cose.
Andrea se mi leggi contattami ... su icq ti ho mandato una richiesta ...
rispondimi sulla posta a 
capitan...@libero.it
 ma ti prego fatti sentire
... non capisco alcune cose !!!
ciao

 termine in un dizionario potrebbe mandarti in un loop infinito).
ROTFL ;-)
Massimo

includere alcun dizionario visto che io tanto non lo so includere ....
Beh..credo che ancora nello standard non sia stata inserita una
funzione bool sensocompiuto(parola).
Il Ghenio
-----
James: Adesso so finalmente cosa provano i panni messi in lavatrice!
Jesse: Avremo bisogno di un candeggio!!
(Team Rocket)
-----

Gli anagrammi si creano molto facilmente per via ricorsiva.
proprio in questi giorni ho trovato un test che consisteva (tra le
altre cose) nel proporre tutti gli anagrammi di una parola; il
problema era che questa parola poteva essere fino a 500 caratteri:
evidentemente con la ricorsione si ha uno stack overflow; come si
potrebbe fare?
Anto
--
Antonio Cuni, 18 anni, studente
Brainbench Certification: 
Master C++: 4.44, higher than 97% of all previous test takers.
Visual Basic 5: 3.06, higher than 77% of all previous test takers.
http://www.brainbench.com/transcript.jsp?pid=1301688

potrebbe fare?
Non esistono parole di 500 lettere... 8)
Luc.

potrebbe fare?
Tutto quello che si fa per via ricorsiva e' fattibile anche per via
iterativa (e viceversa).


Iterando e gestendo uno stack esplicitamente.
Ciao,
Nicola

 iterativa (e viceversa).
Inoltre una parola di 500 simboli con un alfabeto di poche decine di simboli ha
un sacco di anagrammi "uguali". Un metodo che li "elimina" riduce la dimensione
dello stack (o il numero di iterazioni) e aumenta le prestazioni.
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

 potrebbe fare?
con l'iterazione! dove puoi ricorrere, puoi sempre iterare, che è meno
divino, ma richiede meno risorse :-)
ciao

>ROTFL ;-)
scusate l'ignoranza e l'OT, ma cosa significa?


 scusate l'ignoranza e l'OT, ma cosa significa?
Rolling On The Floor Laughing
Massimo

Iterando e gestendo uno stack esplicitamente.
Anche l'idea dietro std::next_permutation sembra
interessante. Data una qualunque permutazione
restituisce la prossima permutazione in ordine
alfabetico (saltando automaticamente i doppioni).


scusate l'ignoranza e l'OT, ma cosa significa?
Che lo ha fatto ridere il riferimento implicito
alla vecchia battuta sulla definizione di ricorsione
presente su dizionario:
   Recursion: see "recursion"
"ROTFL" = "Rolling On The Floor Laughing" ... un
rafforzativo di "LOL" = "Laughing Out Loud"


iterativa (e viceversa).
purtroppo non ho mai potuto studiare la teoria degli algoritmi. Però
se non sbaglio (ne parlava Paolo Marotta qualche tempo fa) un
algoritmo ricorsivo può essere reso iterativo solo se la ricorsione
avviene nell'ultima riga di codice (o qualcosa del genere). Invece nel
caso degli anagrammi avvengono n ricorsioni per ogni chiamata a
funzione; esempio:
anag(anto)=
a+anag(nto)
n+anag(ato)
t+anag(ano) <-- scusate, non era voluta :-)
o+anag(ant)
come si fa ad implementare n ricorsioni in modo iterativo?
cmq usando il C++ la soluzione del problema originario è facile: basta
usare std::next_permutation(). Il problema è che il problema doveva
essere risolto in Pascal o C; già che ci siamo: avete qualche idea su
un algoritmo di permutazione?


 come si fa ad implementare n ricorsioni in modo iterativo?
Rivediamo la versione ricorsiva da te presentata in forma di pseudocodice (T
davanti ai tipi):
T_string_container calcola_anagramma( T_string seme )
    T_string_container risultato;
    for_each T_char c in seme {
        T_string_container parziale = calcola_anagramma( seme without c )
        for_each T_string s in parziale
            risultato.add ( concatena c con s )
    }
    return risultato;
Una equivalente versione iterativa potrebbe essere:
T_string_container calcola_anagramma( T_string seme )
    T_string_container risultato;
    T_string_pair_stack togo;
    togo.push { "", seme }
    do {
        T_string_pair s2 = togo.pop();
        if ( len s2.second is 1 )
            risultato.add ( concatena s2.first con s2.second )
        else
            for_each T_char c in s2.second
                togo.push { concatena s2.first con c, s2.second without c }
    } while ( togo not empty );
    return risultato;
Salvo cavolate dovute al sonno!


un algoritmo di permutazione?
Questa e' una implementazione di next_permutation
tradotta da template a funzione C...
  int next_permutation(char *s,int n)
  {
    int i=n;
    if (n==0 || --i==0)
      return 0; // meno di due elementi... poco da cercare
    for(;;)
    {
      int ip=i;
      if (s[--i]<s[ip])
      {
        // Trovato un elemento piu' piccolo del seguente;
        // costruzione della prossima permutazione in ordine
        // alfabetico
        // Cerca il piu' piccolo maggiore fra i seguenti
        int j=n;
        while (s[i]>=s[--j])
	  ;
        // Scambia questo elemento con quello trovato
        char t=s[i]; s[i]=s[j]; s[j]=t;
        // Rovescia la parte seguente
        while(ip<--n)
        {
          t=s[ip]; s[ip]=s[n]; s[n]=t;
          ip++;
        }
        // Comunica che le permutazioni non sono finite
        return 1;
      }
      if (i==0)
      {
        // Arrivati all'inizio... l'array era ordinato
        // in modo decrescente. Le permutazioni sono finite.
        // Rovescia tutto l'array e segnala il completamento.
        while (i<--n)
        {
          char t=s[i]; s[i]=s[n]; s[n]=t;
          i++;
        }
        return 0;
      }
    }
  }
Nessuna ricorsione e nessuno stack.


           char t=s[i]; s[i]=s[n]; s[n]=t;
[...]
piccolo trucco che funziona con tutti i tipi di dato "compatti"
s[i]^=s[j]; s[j]^=s[i]; s[i]^=s[j];
nel caso dei char, la cosa e' quasi indifferente, ma su oggetti e 
struct belli grossi, e in funzioni ricorsive o in cicli for, ci sono un 
bel po' di allocazioni in meno. funziona anche con i puntatori, e 
logicamente non scambia gli elementi puntati, scambia i puntatori. 
Occhio percio' se l'oggetto puntato fa riferimento a chi lo punta.
piccola dimostrazione a mano:
a = 010010
b = 110101
a ^= b          a = 100111
                b = 110101
 
b ^= a          a = 100111
                b = 010010
a ^= b          a = 110101
                b = 010010 

 avviene nell'ultima riga di codice (o qualcosa del genere).
No; in quel caso (tail-recursion) esiste un semplice algoritmo di
trasformazione tra recursione e iterazione (che e' in genere applicato
dall'optimizer senza che tu te ne accorga, se lui lo ritiene opportuno).
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it
The instructions said to use Windows 98 or better - so I installed FreeBSD.

piccola dimostrazione a mano:
...
Ti posso chiedere dove hai letto che scambiare
usando il triplo xor e' una bella idea ? E' qualcosa
a cui sei giunto da solo ?
Questo "giochetto" e' sicuramente qualcosa di
spiritoso... (ad esempio e' la risposta alla
domanda "come posso scambiare due interi senza
usare variabili di appoggio ?") .. venderlo pero'
come un sistema sensato di fare gli scambi e' un
errore secondo me abbastanza grave.


 a cui sei giunto da solo ?
da solo, programmando per controller integrati su dispositivi embedded 
con capacita' limitate.
e non venitemi a dire per favore che su un telefono portatile, ad 
esempio, mettereste un PIII e 32 MB di ram, poi vi serve una carriola 
per portarvelo dietro.
Certo il discorso viene a cadere riferendosi solo a PC, Workstation e 
comparabili, ma nello standard non rientrano di certo solo questi 
ultimi.

rientrano di certo solo questi ultimi.
Il discorso cade comunque. Anche e soprattutto
per sistemi embedded a 8 bit.
Andrea
PS:
  Qui ormai siamo completamente OT. Non credo
  che il NG sia interessato a questa disquisizione
  sul nulla. Io ritengo la tua posizione su questa
  cosa assolutamente indifendibile (e mi stupisce
  un poco questo accanimento)... se pensi di potermi
  convincere ti pregherei rispondermi in email.
  A meno che questa cosa interessi tutti (dubito molto)


 >potrebbe fare?
Perche pensi di avere problemi di stack overflow ?
considerando che fra una chiamata e l'altra di porti appresso circa 16-20 
byte, moltiplicati per 500 -> qualche kappa, nulla che uno stack di una 
macchina di oggi non possa contenere ( beh' per dirla tutta anche i primi 
picci con 640K ce la facevano !! ) ; anche supponendo che ti copi di volta 
in volta la stringa ( ma noi facciamo programmi efficenti e quindi non 
faremmo mai una cosa del genere ) arrivi a stack dell'ordine di qualche MB 
... una cosa non irragionevole.
Certo permutare una stringa di 500 simboli ... e' una cosa lunga 

 >potrebbe fare?
Con l'affermazione "pochi kappa" forse sono stato un po' ottimista. Rilievi 
sperimentali dal codice che allego mi dicono che servono almeno circa 32K 
di stack ( sotto linux,  con gcc -Wall -O2 )
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class permuta {
  private:
        vector<char>    lock;
        string          str;
        int             len;
        permuta();
  public:
                permuta( const string &s );
        void    ruota( );
};
permuta::permuta( const string &s){
        str = s;
        len=s.length( );
        lock.resize(len);
        for( vector<char>::iterator p = lock.begin( ) ; 
        p != lock.end( ) ; 
        p++ ) 
                (*p)=false;
}
void permuta::ruota( ){
        char    s0;
        stack2=&s0;
        // trova il primo carattere libero
        int i = 0;
        while( i < len && lock[i] ) i++;
        int j = 0;
        int scambiato = false;
        while(true){
                // trova un'altro carattere libero
                while( j < len && lock[j] ) j++;
                if( j >= len ) break;   // finito
                scambiato = true;
                swap( str[i],str[j] );
                // blocchiamolo
                lock[j]=true;
                ruota( );
                lock[j]=false;
                swap( str[i],str[j] );
                j++;
        }
        if( !scambiato ){ cout << str << endl;}
}
int main( ){
        string  s;
        cin>>s;
        permuta p(s);
        p.ruota( );
        return 0;
}

faremmo mai una cosa del genere ) 
ehm... vabbč, ho scritto un algoritmo che č nato male e cresciuto
peggio. Cmq alla fine l'ho risolta, anche in modo efficiente (non vi
sto a spiegare il problema). Direi di finirla qua, visto che credo
siamo OT.
grazie a tutti


dall'optimizer senza che tu te ne accorga, se lui lo ritiene opportuno).
ecco, mi sembrava che qualcosa non quadrasse :-(
ho sempre pensato che mi farebbe bene un po' di informatica teorica,
ma non ho mai avuto il tempo: all'università la studierò, vero?


Non so cosa disse Marotta. Ma se ha detto questo ha detto una cavolata.
devo chiedere scusa a Paolo, avevo male interpretato la sua frase,
come mi ha fatto notare Maurizio Loreti.
anto


ma non ho mai avuto il tempo: all'università la studierò, vero?
Certo, certo... :P
