Newsgroup: it.comp.lang.c++
Titolo: Classe che fa anagrammi

Ciao a tutti, vorrei fare un programmino che legge una stringa e sviluppa
tutti gli anagrammi possibili di senso compiuto....
Sapreste indicarmi dove trovare un dizionario suddiviso x tipo di parola (
verbi, aggettivi, nomi, etc...) e magari sorgenti da esaminare?
è davvero importante...
zao :-) dan.

 esaminare?
spell in italiano, con una qualunque distribuzione linux, ma e' OT
(la classe no, ovviamente :)

tutti gli anagrammi possibili di senso compiuto....
Questo programmino ti genera tutti gli anagrammi, poi il
filtraggio lo fai col vocabolario e se lo trovi ti chiedo di
girarmelo, cortesemente ;)
#include <iostream>
#include <string>
using namespace std ;
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, s.substr(0, i) +
                      s.substr(i + 1), livello);
     }
}
void calcola_anagrammi(string s)
{
     anagramma("", s, s.size());
}
int main()
{
    string my_string;
    cout << "Inserire la stringa da anagrammare : ";
    cin  >> my_string;
    calcola_anagrammi(my_string);
    return 0 ;
}
-- 
Andrea Laforgia (
walkie...@libero.it
)
"Usenet is a strange place" [Dennis Ritchie]

 }
invece della ricorsione, usare std::next_permutation?
qualcosa tipo
std::string stop(s);
std::vector<char> v(s.begin(), s.end());
do {
 std::next_permutation(v.begin(), v.end());
 std::copy(v.begin(), v.end(), s.begin());
 std::cout << s << std::endl;
} while (s!=stop);

 }
invece della ricorsione, usare std::next_permutation?
qualcosa tipo
std::string stop(s);
do {
 std::next_permutation(s.begin(), s.end());


 } while (s!=stop);
mentre facevo tutt'altro ho pensato che cosi' e' leggermente meglio 
(confronto tra bool invece che tra stringhe):
  std::sort(s.begin(),s.end());
  bool cont;
  do {
    std::cout << s << std::endl;
    cont = std::next_permutation(s.begin(), s.end());
  } while (cont);

 girarmelo, cortesemente ;)
per ora ti devi accontentare di un mini_diz del mio prof. di fond.
d'informatica 1...
http://gauguin.info.uniroma2.it/~italiano/Teaching/FondamentiI/dizionario.zi
p
se trovi di meglio avvertimi...
grazie, dan..

 girarmelo, cortesemente ;)
a parte che era meglio usare std::next_permutation, cmq dal momento che 
hai gia` il vocabolario puoi migliorare l'efficienza in un modo simile a 
questo (non compilato):
class anagramma {
  string s;
public:
  anagramma(const string& ss): s(ss) {
    sort(s.begin(), s.end());
  }
  bool operator<(const anagramma& a) {
    return s < a.s;
  }
};
typedef multimap<anagramma, string> mmap;
mmap dict;
void leggi_dict(istream& is)
{
   <per ogni parola letta dal file>
      dict.insert(mmap::value_type(anagramma(parola), parola));
}
void stampa_anagrammi(const string& s)
{
   pair<mmap::const_iterator, mmap::const_iterator> r;
   r = dict.equal_range(anagramma(s));
   transorm(r.first(), r.second(), ostream_iterator<string>(cout, "\n"), 
select2nd<mmap::value_type>());
   // nota: select2nd non e` standard
}
ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

a parte che era meglio usare std::next_permutation,
Si' ma, che ci vuoi fare, a me le cose piace costruirmele da
zero... std::next_permutation, molto interessante...


std::next_permutation, molto interessante
Comunque in molti casi come questo in cui vuoi fare degli anagrammi
puň non essere il massimo, ad esempio se usi il un vocabolario il
codice di Antonio č meglio, un altro esempio che mi viene in mente era
un esercizio delle Olimiadi di Informatica dell'anno scorso. In quel
caso non c'era un vocabolario ma delle condizioni da rispettare (ad
esempio non piů di due consonanti consecutive mi pare) per cui
effettuare dei controlli prima aumentava notevolmente le prestazioni
(anche perché se non ci fossero limitazioni vorrei sapere come
riuscire a generare e scrivere su disco tutti gli anagrammi di una
stringa di 500 caratteri in 5 secondi).
-- 
Marco Barisione

stringa di 500 caratteri in 5 secondi).
???


  }
Utilizzando un std::vector<char> probabilmente si ottengono
prestazioni migliori rispetto a quelle di std::string.
Il Ghenio
---------
// TODO: Place your ass here

 stringa di 500 caratteri in 5 secondi).
sicuramente col multimap di cui sopra no (e dubito pure avendo a 
disposizione un cray e dischi con trasfer rate al top della 
tecnologia). 
dovresti poter leggere un dizionario di milioni di frasi di senso 
compiuto, ordinate come prima, e credo che per certe cose sia meglio un 
DBMS che una struttura o un programma C++ 

 ???
http://ioi.dsi.unimi.it
 per maggiori info.


 da usare.
next_permutation e` molto veloce? Se io ho una parola di 10 caratteri e 
uso next_permutation dovro` esaminare un numero di anagrammi pari a
10! = 3.628.800. Non male come efficienza.
Al contrario un lookup in una map, multimap, set, multiset e` garantito 
avere una complessita` computazionale di log(N), dove N e` il numero di 
elementi nella map (200.000 in questo caso); dato che log(200.000) ~= 
17.6 direi che e` nettamente piu` conveniente.
Nota che un discorso del genere ha senso se pensiamo di anagrammare 
molte parole, altrimenti potrebbe non valere la pena di costruire 
l'intera multimap; anche se cmq nel caso di una parola con 10 lettere 
immagino che sia lo stesso piu` conveniente che non generare tutte le 
permutazioni.
Nota che, tra l'altro, la soluzione "immediata che usa next_permutation 
non funziona:
void stampa_anagrammi(const string& str)
{
   string s(str);
   sort(s.begin(), s.end());
   do {
      cout << s << endl;
   } while ( next_permutation(s.begin(), s.end()) );
}
Infatti il codice qua sopra stamperebbe alcune parole piu` volte, nel 
caso la stringa di partenza avesse alcuni caratteri ripetuti (ad esempio 
"pippo").


 prestazioni migliori rispetto a quelle di std::string.
Parli del sort? Io non vi vedo una gran differenza:
[anto@localhost tmp]$ g++ -v
Reading specs from /usr/local/lib/gcc-lib/i686-pc-linux-gnu/3.0/specs
Configured with: /usr/src/gcc-3.0/configure --enable-languages=c++
Thread model: single
gcc version 3.0
[anto@localhost tmp]$ cat test.cc
#include <vector>
#include <string>
#include <algorithm>
#include <ctime>
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
  vector<char> v;
  ifstream f("prova.txt");
  copy(istream_iterator<char>(f),
       istream_iterator<char>(),
       back_inserter(v) );
  string s(v.begin(), v.end());
  clock_t begin_time;
  clock_t end_time;
  begin_time = clock();
  sort(v.begin(), v.end());
  end_time = clock();
  cout << "Vector: " << (double)(end_time-begin_time)/CLOCKS_PER_SEC << 
" secondi\n";
  begin_time = clock();
  sort(s.begin(), s.end());
  end_time = clock();
  cout << "String: " << (double)(end_time-begin_time)/CLOCKS_PER_SEC << 
" secondi\n";
}
[anto@localhost tmp]$ wc prova.txt
  66909  253879 2185758 prova.txt
[anto@localhost tmp]$ for i in `seq 1 10`; do  echo "------ Prova $i 
------"; ./test; done
------ Prova 1 ------
Vector: 3.37 secondi
String: 3.38 secondi
------ Prova 2 ------
Vector: 3.5 secondi
String: 3.57 secondi
------ Prova 3 ------
Vector: 3.38 secondi
String: 3.4 secondi
------ Prova 4 ------
Vector: 3.45 secondi
String: 3.85 secondi
------ Prova 5 ------
Vector: 3.39 secondi
String: 3.37 secondi
------ Prova 6 ------
Vector: 3.37 secondi
String: 3.7 secondi
------ Prova 7 ------
Vector: 3.38 secondi
String: 3.38 secondi
------ Prova 8 ------
Vector: 3.39 secondi
String: 3.52 secondi
------ Prova 9 ------
Vector: 3.44 secondi
String: 3.4 secondi
------ Prova 10 ------
Vector: 3.38 secondi
String: 3.41 secondi
[anto@localhost tmp]$
In effetti in queste prove spesso vector e` leggermente meglio di 
string, ma in altre che ho fatto (senza monitorarle) string era spesso 
migliore, quindi...


 esempio "pippo").
non funziona? 
non so quale versione di next_permutation tu usi, ma...
ioppp
ipopp
ippop
ipppo
oippp
opipp
oppip
opppi
piopp
pipop
pippo
poipp
popip
poppi
ppiop
ppipo
ppoip
ppopi
pppio
pppoi

coniugate e declinazioni dei verbi)
Non penso proprio che l'OP volesse tutte le parole di una lingua ma le
più comuni.
-- 
Marco Barisione (ICQ 84277092)

 più comuni.
se vuoi _tutti_ gli anagrammi, non c'e' altro verso: o te le carichi 
tutte, oppure filtri le permutazioni con un prog apposito. 
inoltre le forme verbali per ogni verbo sono circa 80 nella forma base, 
considerando poi che possono avere i pronomi legati (mangiandola, rasarsi,
etc..) sono loro che fanno salire molto il numero, non le parole inusuali

 tutte, oppure filtri le permutazioni con un prog apposito.
quale metodo pensi mi convenga ?
Dan
PS. Grazie a tutti del prezioso aiuto...

 String: 3.57 secondi
[cut]
pensandoci bene se abbiamo un vector<char> o una string in un sistema in 
cui i char sono piccoli (sul mio intel sono a 8 bit) la cosa migliore in 
assoluto e` non utilizzare per nulla std::sort: implementandosi in 
proprio l'algoritmo di distribution counting abbiamo prestazioni 
nettamente superiori; ad esempio questa funzione:
void sort(vector<char>& v)
{
  int count[255];
  for(int i=0; i<255; i++)
    count[i]=0;
  for(int i=0; i<v.size(); i++)
    count[v[i]]++;
  int pos=0;
  cout << v.size();
  for(int i=0; i<255; i++)
    for(int j=0; j<count[i]; j++)
      v[pos++]=i;
}
sul mio sistema impiega circa 0.6 secondi a fare quello che std::sort 
faceva in circa 3.3 secondi...


 non so quale versione di next_permutation tu usi, ma...
hai ragione, ho sbagliato.


 la singola chiamata e' sicuramente + veloce, 
[cut]
mi sono dimenticato di metterlo nel post precedente; questo codice qua:
  std::string s="0123456789";
  std::sort(s.begin(), s.end());
  while (std::next_permutation(s.begin(), s.end()))
        ;
compilato con g++ 3 e fatto girare sul mio athlon 800 impiega circa 7 
secondi a terminare; se aggiungo *un solo* carattere alla stringa impiega
1 minuto e 23 secondi circa; se ne aggiungo un altro (e siamo a 12) ci 
mette circa 15 minuti e 37 secondi. Secondo te quanto ci mette con 20 
caratteri?


ogni anagramma possibile con tutte le N parole del dizionario;
Infatti non e' questa la via migliore.
Andrebbe creata l'associazione tra una firma e le parole
associate a quella firma.  Per esempio, le parole "lavagna"
e "valanga" hanno la stessa firma "aaagln" (le lettere della
parola scritte in ordine alfabetico).
L'associazione e' del tipo:
aaagln ---> "valanga", "lavagna".
Quando viene inputata una parola, se ne calcola la firma e
si ottengono i suoi anagrammi (con "anagrammi" si intende
l'insieme delle parole di senso compiuto presenti nel
vocabolario).


 caratteri?
Senza entrare nel merito del discorso, mi sembrano valori altini i tuoi.
Sul mio PIII667 con borland c++ compiler 5.5.1 su Win2000 pro
e questo codice:
---codice---
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
using std::cout;
using std::endl;
using std::clock_t;
using std::clock;
int main()
{
    clock_t start,end;
    start=clock();
    std::string s="0123456789";
    std::sort(s.begin(), s.end());
    while (std::next_permutation(s.begin(), s.end()) );
    end=clock();
    cout << s << endl;
    cout << "Tempo impiegato= " << double(end-start) << " ";
    cout << CLOCKS_PER_SEC << "-esimi di secondo"  << endl;
    s += "a";
    start=clock();
    std::sort(s.begin(), s.end());
    while (std::next_permutation(s.begin(), s.end()) );
    end=clock();
    cout << s << endl;
    cout << "Tempo impiegato= " << double(end-start) << " ";
    cout << CLOCKS_PER_SEC << "-esimi di secondo"  << endl;
    s += "b";
    start=clock();
    std::sort(s.begin(), s.end());
    while (std::next_permutation(s.begin(), s.end()) );
    end=clock();
    cout << s << endl;
    cout << "Tempo impiegato= " << double(end-start) << " ";
    cout << CLOCKS_PER_SEC << "-esimi di secondo"  << endl;
}
---fine codice---
Ottengo questo output:
0123456789
Tempo impiegato= 511 1000-esimi di secondo
0123456789a
Tempo impiegato= 5538 1000-esimi di secondo
0123456789ab
Tempo impiegato= 72224 1000-esimi di secondo
...che mi pare un po' meglio
(ma comunque non cambia il senso del tuo discorso...)
--
Gerolamo

 parola scritte in ordine alfabetico).
ok, le hash sappiamo tutti che sono ottime per queste cose
pero' riscrivere un intero vocabolario, quando esistono implementazioni 
di spellcheck gratuite, efficienti e facilmente estendibili, mi sembra 
uno spreco... 
Passare un file con varie parole ad aspell e farlo processare, sapendo 
che funziona bene, senza errori e che non ci devo mettere mano, lo 
preferisco a farmi una hash, mantenere un vocabolario, e usarlo
poi se in un futuro vedro' che questi benedetti anagrammi sono troppo 
lenti, pazienza, lo faro', ma una soluzione funzionante del problema io 
ce l'ho dal primo post su next_permutation. mi fate sapere quando avete 
implementato la vostra, e vediamo quanti anagrammi di parole di 10 
lettere tutte differenti nel frattempo ho calcolato?-)
inoltre, per Antonio Cuni, il calcolo fattoriale vale solo per parole 
con tutti i caratteri differenti. trovami + 4 parole di 10 lettere o 
piu' che non hanno ripetizioni... e magari prova a compilare i tuoi 
programmi c++ che devono essere veloci con qualche ottimizzazione del 
g++, queste possono esserti utili:
-fomit-frame-pointer 
-fexpensive-optimizations 
-fgcse 
-frerun-loop-opt 
-funroll-all-loops 
-fmove-all-movables 
-march=<latua> 
-s 
-O9 
-fno-rtti (con raziocinio)
-fno-exceptions (idem)
un'ultima cosa, sempre per il g++ 3, occhio che la libreria e' gia' 
stata aggiornata piu' volte, se lo usi frequentemente abbi cura di 
upgradarla, e' stata migliorata un bel po'

 preferisco a farmi una hash, mantenere un vocabolario, e usarlo
Vedi sopra.
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 Tempo impiegato= 72224 1000-esimi di secondo
tanto per rivalutare linux :
cat  /proc/cpuinfo                            
[...]
model name      : AMD Athlon(tm) Processor
cpu MHz         : 857.639
gcc:
Reading specs from /usr/local/lib/gcc-lib/pc-gnu-linux/2.95.3/specs
gcc version 2.95.3 20000316 (release)
opzioni: 
-fomit-frame-pointer -fexpensive-optimizations -fgcse -frerun-loop-opt 
-funroll-all-loops -fmove-all-movables -march=i686 -s -O9
-fno-rtti -fno-default-inline -fno-exceptions -ansi 
output:
0123456789
Tempo impiegato= 380000 1000000-esimi di secondo
0123456789a
Tempo impiegato= 4170000 1000000-esimi di secondo
0123456789ab
Tempo impiegato= 50970000 1000000-esimi di secondo

 ha creato la libreria e buona notte).
be', se mi si comincia a parlare di timings... e se estendiamo il 
discorso alla real life, io ho "consegnato" 3 giorni fa, voi quando 
stimate? inoltre piu' o meno per quella data, se il mio cliente/datore 
vuole, avro' realizzato una versione analoga alla vostra, piu' 
efficiente della mia, che pero' intanto ha funzionato per 
giorni(mesi?). Il tutto applicando i pattern di design per la 
progettazione KISS, insieme a Make It Run Make It Right Make It Fast

 ha creato la libreria e buona notte).
be', se mi si comincia a parlare di timings... 
io non creddo che usare i filtri alla maniera di Unix non sia 
realizzare da zero. mi appoggio solamente a cose gia' esistenti, e 
provate, invece di ripartire da capo ogni volta.


 Tempo impiegato= 50970000 1000000-esimi di secondo
0123456789
Tempo impiegato= 300000 1000000-esimi di secondo
0123456789a
Tempo impiegato= 3190000 1000000-esimi di secondo
0123456789ab
Tempo impiegato= 39190000 1000000-esimi di secondo
un 25% circa in meno sul totale

 vocabolario).
tra l'altro, ho provato il codice di cuni, con un file di 2.000.000 di 
parole, su una macchina con 512 MB di memoria, e' andato out of memory 
dopo circa 19 secondi
come dicevo, per una tale mole di dati, e' meglio un DBMS

fa, voi quando stimate? 
Non pensavo che fosse un compito in classe, rilassati...


 Non pensavo che fosse un compito in classe, rilassati...
rilassatissimo, era solo per dire che a volte un compromesso tra  
efficienza/codice subito pronto e' conveniente, accontenta il cliente e 
ti permette di continuare a lavorare su di una versione che, intanto, va

 upgradarla, e' stata migliorata un bel po'
ok, grazie.


 e questo codice:
bisogna vedere quanto il compilatore ha ottimizzato.
E` ovvio che il ciclo
while( next_permutation(s.begin(), s.end() )
        ;
non produce alcun effetto visibile, quindi un compilatore abbastanza 
furbo puo` direttamente toglierlo e impiegare 0 secondi (anche se non 
credo esistano compilatori cosi` furbi).
Io ho compilato senza alcuna ottimizzazione, perche` volevo vedere 
quanto tempo impiegava a generare tutte le permutazioni.


zao :-) dan.
mi dispiace non conosco molto bene la teoria degli algoritmi; la mia
idea sarebbe di trovare gli invarianti per permutazione delle parole
(lunghezza della stringa e somma dei valori dei caratteri della
stringa) e eseguire ordinamenti nel vocabolario solo per le parole
candidate (che hanno stessa lunghezza e stessa somma).
Se avete un dizionario di parole italiane separate sempre con lo
stesso carattere nel mio caso il carattere ascii 10 (io ho il
dizionario di italiano di 4spell di TeX) potete provare ad adattare il
seguente programma che impiega pochi secondi per trovare un anagramma
dal mio pentium 100 e vocabolario 3MB (infatti non conosco neanche in
C++ :(  )
Sarei grato se scrivete gli errori di programmazione che faccio
#include <stdio.h>
#include <string.h>
/*Stampa gli anagrammi della parola che riceve
 per argomento c'e' bisogno del dizionario*/
void swap(unsigned char* v, int i, int j)
{ unsigned char temp;
  temp=v[i]; v[i]=v[j]; v[j]=temp;
}
/* quicksort: ordina v[left]...v[right] in ordine crescente */
void qsort(unsigned char* v, int left, int right)
{int i, last;
 void swap(unsigned char* v, int i, int j);
 if(left>=right) return;
 swap(v, left, (left+right)/2);
 last=left;
 for(i=left+1; i<=right; i++)
        if(v[i]<v[left]) swap(v, ++last, i);
 swap(v, left, last);
 qsort(v, left, last-1);
 qsort(v, last+1, right);
}
int confronta(unsigned char* vv,unsigned char* p, int len)
{short i;
 for(i=0;i<len && vv[i]==p[i];++i);  
 if(i==len) return 1;
 else return 0;
}
int prendi_parole(unsigned char* p, int len, int sommap, 
                  unsigned char carattere, FILE* tmp )
{unsigned char a[200], b[200];
 int somma;
 register short c; 
 int i,j;
for(;;)
  {i=0; somma=0;
   while( (c=fgetc(tmp))!=EOF && i < 199 && c!=carattere)
                                    {a[i++]=c; somma+=c;}
   a[i]='\0';
   if(i==199) {printf("problemi di lettura dal dizionario (c :) )\n");
               return -1;
              }/*v[0] v[1] ... v[len-1] v[len]=='\0'*/
   if(len==i && somma==sommap)
                    {strcpy(b,a);
                     qsort(b, 0, len-1);
                     if(confronta(b, p, len)) printf("%s ", a);
                    }
   if(c==EOF) return 0;
  }
}
int main(int argc, char** argv)
{int i, h, len;
 FILE * tmp;
 int sommap=0;
 unsigned char v[200];
 if(argc!=2 || (len=strlen(argv[1]))>199)
   {printf("Uso: Mio_nome parola_da_anagrammare \n");
    return -1;
   }
 if( (tmp=fopen("dizionario","rb"))==NULL)
   {printf("Trovo problemi a aprire il dizionario \n");
    return -1;
   }
 strcpy(v, argv[1]);
 qsort(v, 0, len-1);
 for(i=0;(h=v[i])!='\0'; i++)
                           sommap+=h; 
/*c==10 è il carattere di separazione 
     parole del dizionario*/
 prendi_parole( v,  len, sommap, 10, tmp);/*10 è char di divisione*/
 printf("\n");
 return 0;
}
C:\prog\capitolo4-8>anagrammi mare
arem arme erma mare mera rame rema
Saluti
     jjkk

stringa) e eseguire ordinamenti nel vocabolario solo per le parole
mi correggo: il vocabolario non č ordinato e nel mio caso si chiama
"dizionario"

ah, be', ma tu non eri quello che non voleva ricostruire da capo un os? 
A cosa ti stai riferendo ?
Per la precisione, io il mio s.o. me lo sono scritto, si
chiama ALOS e sta tutto su un dischetto.


On Fri, 08 Feb 2002 18:39:22 GMT, j...@jk.jk (jk) wrote:
[cut]
_______________________________________
C:\prog\capitolo4-8>anagrammi  pirateria
paritarie pirateria riapriate ripariate
  :)))

#include <stdio.h>
#include <string.h>
/*Stampa gli anagrammi della parola che riceve
 per argomento c'e' bisogno del dizionario*/
void swap(unsigned char* v, int i, int j)
{ unsigned char temp;
  temp=v[i]; v[i]=v[j]; v[j]=temp;
}
/* quicksort: ordina v[left]...v[right] in ordine crescente */
void qsort(unsigned char* v, int left, int right)
{int i, last;
 if(left>=right) return;
 swap(v, left, (left+right)/2);
 last=left;
 for(i=left+1; i<=right; i++)
        if(v[i]<v[left]) swap(v, ++last, i);
 swap(v, left, last);
 qsort(v, left, last-1);
 qsort(v, last+1, right);
}
/* p->parola da cercare, file->nome del dizionario*/
int prendi_parole(unsigned char* p, 
                  const unsigned char carattere, char * file )
{unsigned char a[200], b[200], g[200];
 short  len, sommap=0;
 register short c, somma, i;
 FILE * tmp;
 if( (tmp=fopen(file,"rb"))==NULL)
   {printf("Trovo problemi a aprire il dizionario \n");
    return -1;
   }
 for(i=0;(c=p[i])!='\0'; i++)
                         sommap+=c; 
 len=i;
 if(len>198) {printf("striga troppo lunga \n"); return -1;}
 strcpy(g,p);
 qsort(g, 0, len-1);
for(;;)
  {i=0; somma=0;
   while( (c=fgetc(tmp))!=EOF && i < 199 && c!=carattere)
                                    {a[i++]=c; somma+=c;}
   a[i]='\0';
   if(i==199) 
      {printf("Dizionario: non riconosco il char separatore\n");
       return -1;
     }/*v[0] v[1] ... v[len-1] v[len]=='\0'*/
   if(len==i && somma==sommap)
                    {strcpy(b,a);
                     qsort(b, 0, len-1);
                     if(!strcmp(b, g)) printf("%s ", a);
                    }
   if(c==EOF) return 0;
  }
}
int main(int argc, char** argv)
{if(argc!=2 || strlen(argv[1])>199)
   {printf("Uso: Mio_nome parola_da_anagrammare \n");
    return -1;
   }
/*c==10 è il carattere di separazione 
     parole del dizionario*/
 prendi_parole( argv[1], 10, "dizionario");/*10 è char di divisione*/


  printf("\n");
se questo e' c++ che insegnano a scuola, allora per il java cosa 
intendono, il cobol?

On Sun, 10 Feb 2002 09:48:27 GMT, j...@jk.jk (jk) wrote:
#include <stdio.h>
#include <string.h>
/*Stampa gli anagrammi della parola che riceve
 per argomento c'e' bisogno del dizionario*/
void swap(unsigned char* v, int i, int j)
{ unsigned char temp; temp=v[i]; v[i]=v[j]; v[j]=temp;  }
/* quicksort: ordina v[left]...v[right] in ordine crescente */
void qsort(unsigned char* v, int left, int right)
{int i, last;
 if(left>=right) return;
 swap(v, left, (left+right)/2);
 last=left;
 for(i=left+1; i<=right; i++)
        if(v[i]<v[left]) swap(v, ++last, i);
 swap(v, left, last);
 qsort(v, left, last-1);
 qsort(v, last+1, right);
}
int prendi_parole(unsigned char* p, 
                  const unsigned char carattere, char * file )
{unsigned char a[200], b[200], g[200];
 short  len, sommap=0;
 register short c, somma, i;
 FILE * tmp;
 for(i=0;(c=p[i])!='\0'; i++)
                         sommap+=c; 
 len=i;
 if(len>198) {printf("striga troppo lunga \n"); return -1;}
 strcpy(g,p);
 qsort(g, 0, len-1);
 if( (tmp=fopen(file,"rb"))==NULL)
   {printf("Trovo problemi a aprire il dizionario \n");
    return -1;
   }
for(;;)
  {i=0; somma=0;
   while( (c=fgetc(tmp))!=EOF && i < 199 && c!=carattere)
                                    {a[i++]=c; somma+=c;}
   a[i]='\0';
   if(i==199) 
     {printf("Dizionario: non riconosco il char separatore\n");
      fclose(tmp);
      return -1;
     }/*v[0] v[1] ... v[len-1] v[len]=='\0'*/
   if(len==i && somma==sommap)
                    {strcpy(b,a);
                     qsort(b, 0, len-1);
                     if(!strcmp(b, g)) printf("%s ", a);
                    }
   if(c==EOF) break;
  }
 fclose(tmp);
 return 0;
}
int main(int argc, char** argv)
{if(argc!=2 || strlen(argv[1])>199)
   {printf("Uso: Mio_nome parola_da_anagrammare \n");
    return -1;
   }
/*c==10 č il carattere di separazione 
     parole del dizionario*/
 printf("\nUscita=%d", 
     prendi_parole( argv[1], 10, "dizionario"));/*10 č char di




mi piace andare ot :) 
non mi vorrai privare di questo piacere?
Ma tu perchč non riprendi l'interessante discussione con gli altri in
questo trend?

 questo trend?
si dovrebbe chiamare thread, se non erro, comunque che altro aggiungere?
laforgia e cuni sono convinti che convenga fare una hash e farsi un 
dizionario, da caricare in memoria con una multimap, per velocizzare la 
ricerca
io dico che un dizionario di milioni di parole richiede troppo lavoro 
per essere il primo approccio, e che occorre troppa memoria usare una 
struttura c++ per contenerlo: un dbms che interroga un db di parole e' 
senz'altro meno esoso in termini di memoria, anche se e' (sicuramente) 
piu' lento.

 void qsort(unsigned char* v, int left, int right)
a parte che in C++ sarebbe meglio usare std::sort, ma forse non sai che 
la libreria standard del C fornisce gia` una funzione qsort, quindi ti 
conviene usare quella.


io dico che un dizionario di milioni di parole richiede troppo lavoro 
"milioni di parole"  quanti MB sono? 100 ? 1000 ?
Se sono nell'ordine di 9 o 10 MB non capisco  il problema e non lo
voglio capire <OT ON>perchč (sto studiando il C e non il C++) <OT OFF>
Saluti

quella originale,
concordo bisogna che il vocabolario abbia le parole ordinate per
lunghezza (o forse anche per lunghezza e qualche altro parametro per
esempio la presenza di vocali e il loro numero).
Supponiamo di avere una parola di lunghezza n memorizzata in char p[n]
Si prenda la prima porola del vocabolario compatibile di lunghezza n e
sia memorizzata in char v[n]  siano vv[n] pp[n] due stringhe si svolga
vv=v;
pp=p;
ordina(vv);
ordina(pp);
for(i=0;i<n;i++) if(vv[i]!=pp[i]) break; 
if(i==n-1) salva(vv[n]);
si prosegua con la seconda parola compatibile del vocabolario di
lunghezza n e così via.
allora aalaro --> aallor    aaalor

complessità nel caso di dizionari linguistici (come a me pare)?
ove n è il numero di parole del dizionario 'compatibili' con la parola
in ingresso (stessa lunghezza ecc)


Secondo me il vocabolario sarebbe ben strutturato con un albero 27-ario (26
sono le lettere + terminatore) di questo tipo
esempio:
                 a                  b               c
                /  \ ........     .......          .......
               b   c .......
              / \ ...........
            a  ...........
         / / \ \
       ? c    t  z
        / |   /  \  \
      o  i  e    i  i
     /   |  |       \   \
   ?    ? ?        n   a
                     / \    \
                    i    o  ?
                   /       \
                 ?         ?
aba?, abaci?, abaco?, abate?, abati?, abatino?, abazia?
?=terminatore
tralasciando lo spazio occupato dai puntatori(21) , con 22 caratteri ho
memorizzato 7 parole che ne occupano 43, in pratica uso la radice di una
parola una volta sola in modo da evitare di occupare troppo spazio con le
cogniugazioni dei verbi il caso ed il genere delle parole, ma soprattutto se
devo cercare una parola di lunghezza n faccio al massimo n passi
indipendentemente dalla dimensione del dizionario.
Il problema è che un puntatore di solito occupa molto piu spazio di un char,
bisorrebe ingegnarsi a ridurre questo costo, ammesso che sia un costo di
molto superiore, ad esempio usando i tre byte superiori per determinare lo
spiazzamento rispetto ad una base (ma occorre avere un blocco contiguo della
dimensione del vocabolario) ed il byte inferiore per il carattere di cui il
bit piu alto potrebbe indicare che esiste un terminatore.
Che ne dite?

 Che ne dite?
che sei vicino al modo in cui lavora aspell, solo che lo fa su file, e 
usando degli indici

 complessità nel caso di dizionari linguistici (come a me pare)?
non sono cosi` esperto da pronunciarmi sull'algoritmo ottimo.
Cmq se devi effettuare un solo anagramma direi che la complessita` e` 
nell'ordine di O(N), con N numero di parole totali nel vocabolario.
Per migliorare le prestazioni si puo` decidere di organizzare in maniera 
differente il vocabolario: ad esempio suddividere le parole per 
lunghezza e iniziale; in questo caso la complessita` e` dell'ordine di 
O(n), con n numero di parole "compatibili", come hai detto anche tu. Cmq 
nota che, grosso modo, n dipende in maniera lineare da N, quindi la 
complessita` e` ancora O(N) (anche se le prestazioni sono senza dubbio 
migliori).
Se devi effettuare piu` di un anagramma e` possibile ridurre la 
complessita` ad O(lgN) (ad esempio usando map - indipendentemente dal 
fatto che questa sia una soluzione "pratica" o meno).


 Che ne dite?
avevo proposto un metodo del genere qualche mese fa su 
it.scienza.matematica. Come complessita` e` senza dubbio la migliore, 
dato che e` lineare sul numero di lettere della parola, ma ci sono 
alcune complicazioni: la memoria occupata (come hai fatto anche notare 
tu) e la difficolta` di implementazione (non esagerata ma neppure 
banale).
Certo che complicando ulteriormente la struttura dati e, ad esempio, 
memorizzare l'albero in parte in memoria e in parte su disco potrebbe 
essere la soluzione migliore.


riferirsi al caso peggiore
Be', non e' del tutto vero, la complessita' computazionale
si calcola per il caso peggiore e per il comportamento
atteso.


 atteso.
 
cosa vuol dire "per il comportamento atteso"?
Cmq, per completezza, ci sono dei casi in cui si misura la complessita` 
nel caso medio: esempio classico e` il quicksort che nella stragrande 
maggioranza dei casi e` O(N lgN) mentre nel caso peggiore e` O(N^2).


 nel caso medio: 
Si misura *sempre* ed e' questa che va tenuta maggiormente
in considerazione.  E' cio' che intendo per "comportamento atteso".
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 peggiore e` O(N^2).
forse fai confusione: la complessita' e' algoritmica, e dipende solo 
dall'algoritmo, non dalle medie dei casi concreti di applicazione. 
quella di qsort e' O(N^2)
Mediamente pero' il numero di operazioni svolte da qsort risulta 
dell'ordine di grandezza di N logN. 
a rigor di termini pero' la complessita' e' sempre O(N^2)
in pratica qsort e' un algoritmo di O(N^2), ma di una efficienza nel 
caso medio che lo rende paragonabile ad uno di complessita' O(N log N) 
(risultando molto spesso migliore)

 a rigor di termini pero' la complessita' e' sempre O(N^2)
a rigor di termini la complessita` non *e`* O(N^2) ma semmai 
*appartiene* a O(N^2); come del resto e` perfettamente sensato dire che 
il qsort appartiene a O(N^3), O(2^N) e O(N!).
Per essere il piu` precisi possibile possiamo dire che nel caso peggiore 
appartiene a tetha(N^2).


 peggiore appartiene a tetha(N^2).
sei senz'altro piu' fresco di me di studi... che io mi ricordi, la 
complessita' asintotica e' sempre calcolata nel caso peggiore