Come creare un programmino x anagrammi

[SkyWarrior]

raga salve a tutti è la prima volta ke scrivo in questa sezione e lo faccio x kiedere il vostro aiuto sulla programmazione di un programmino ke mi permetta inserendo alcune lettere di creare delle parole usandole... ora il problema sta nel fatto ke nn ho mai programmato . Vi prego aiutatemi...



P.S. mi servirebbe se possibile ke faccia anke parole in latino . HELP ME!!!

[@@mikele90@@]

raga salve a tutti è la prima volta ke scrivo in questa sezione e lo faccio x kiedere il vostro aiuto sulla programmazione di un programmino ke mi permetta inserendo alcune lettere di creare delle parole usandole... ora il problema sta nel fatto ke nn ho mai programmato . Vi prego aiutatemi...



P.S. mi servirebbe se possibile ke faccia anke parole in latino . HELP ME!!!

nn ho ben capito,cmq nn è propio corto,dopo fai qualche esmpio.cmq n credo ci sia gente disponibile(a meno che nn escono fuori dei soldi)

[Chobeat]

è un lavoro da pochi minuti.

un input di tot lettere, il programma genera tutte le combinazioni casuali possibili e le controlla con quelle di un dizionario qualsiasi

[SkyWarrior]

si e mi spighi cm si fa?

[nico402]

te l'ha appena spiegato.. per prima cosa però ti serve un file con tt le parole in latino. se no è un pò dura come cosa..

[marcelloma]

è un lavoro da pochi minuti.

un input di tot lettere, il programma genera tutte le combinazioni casuali possibili e le controlla con quelle di un dizionario qualsiasi

questo e' un metodo che funziona, un altro metodo e' quello di scorrersi tutte le parole del dizionario una volta sola e salvarsi quelle che hanno le stesse lettere.Forse il tuo metodo e' impiegherebbe tempo O(n!*logN) (dove n e' la lunghezza della parola , N il numero di parole nel dizionario) quindi esponenziale nel numero di lettere della parola, il mio O(N*n) (N volte il confronto con la parola di lunghezza n).

@SkyWarrior: non possiamo spiegarti come si fa se prima non conosci la sintassi di un qualsiasi linguaggio di programmazione.Comincia ad impararne uno ma parti dalle cose semplici tipo fai una calcolatrice.

[nico402]

questo e' un metodo che funziona, un altro metodo e' quello di scorrersi tutte le parole del dizionario una volta sola e salvarsi quelle che hanno le stesse lettere.Forse il tuo metodo e' impiegherebbe tempo O(n!*logN) (dove n e' la lunghezza della parola , N il numero di parole nel dizionario) quindi esponenziale nel numero di lettere della parola, il mio O(N*n) (N volte il confronto con la parola di lunghezza n).

@SkyWarrior: non possiamo spiegarti come si fa se prima non conosci la sintassi di un qualsiasi linguaggio di programmazione.Comincia ad impararne uno ma parti dalle cose semplici tipo fai una calcolatrice.

contando comunque che N nel suo caso non sarà più lungo di 10/15 e che l'N invece sarà molto grande, direi che il metodo migliore è quello O(n!*logN) dato che con n piccoli e con N grandi risulta comunque meglio il metodo calcoloso

[marcelloma]

contando comunque che N nel suo caso non sarà più lungo di 10/15 e che l'N invece sarà molto grande, direi che il metodo migliore è quello O(n!*logN) dato che con n piccoli e con N grandi risulta comunque meglio il metodo calcoloso

esatto giusta osservazione
edit: però gia' con 15 lettere non so quanto convenga, 15! e' 1.307.674.368.000 , probabilmente un vocabolario ha meno termini

[nico402]

esatto giusta osservazione
edit: però gia' con 15 lettere non so quanto convenga, 15! e' 1.307.674.368.000 , probabilmente un vocabolario ha meno termini

ma 15 lettere sono tantissime.. è + probabile gli serva avere 6 o 7 lettere. non so quante parole in latino siano + lunghe..

[Chobeat]

si ma poi serve solo a lui, non è che deve andarlo a vendere in giro. se per una parola lunga ci mette 3 minuti, non muore nessuno... o così o si attacca

[_Tommo_]

si ma poi serve solo a lui, non è che deve andarlo a vendere in giro. se per una parola lunga ci mette 3 minuti, non muore nessuno... o così o si attacca

IMHO si potrebbe usare l'ordine alfabetico per cercare, invece che comparare tutte le ipotesi a tutte le parole...

es:

asgsdf

trovi la parola nel dizionario che starebbe prima, se esistesse, e quella che sta dopo. In mezzo c'è quella che cerchi
Se in mezzo non c'è niente la parola non esiste.
Credo che questo metodo possa essere molto rapido

Cmq se il tale non ha mai programmato lo vedo decisamente difficoltoso da farsi in tempi stretti, perchè per quanto sia banale è un lavoro pallosissimo e lungo

[marcelloma]

IMHO si potrebbe usare l'ordine alfabetico per cercare, invece che comparare tutte le ipotesi a tutte le parole...

es:

asgsdf

trovi la parola nel dizionario che starebbe prima, se esistesse

e come la trovi? (con che algoritmo veloce intendo)
invece si potrebbe usare una struttura dati "dizionario" (un albero ordinato) oppure semplicemente un vettore ed applicare la Ricerca Binaria

[nico402]

e come la trovi? (con che algoritmo veloce intendo)
invece si potrebbe usare una struttura dati "dizionario" (un albero ordinato) oppure semplicemente un vettore ed applicare la Ricerca Binaria

un dizionario in tero da tenere in memoria è un pò complicato mi sa... metti ccaso che facciamo per ogni parola un char[20]. e il resto lo allochiamo anche dinamicamente se vuoi. direi che a metà, o prima, ci troviamo senza memoria e il programma da un segfault :P

l'unica quindi è la ricerca sequenziale. mettendo in un vettore un numero massimo di N parole che poi verranno cambiate a fine ricerca fino ad arrivare sul fondo

[_Tommo_]

e come la trovi? (con che algoritmo veloce intendo)
invece si potrebbe usare una struttura dati "dizionario" (un albero ordinato) oppure semplicemente un vettore ed applicare la Ricerca Binaria

Beh banale se il dizionario è ordinato alfabeticamente.

"ciao"

1 trovi c
2 in c trovi i
3 in i trovi a
4 in a trovi o
unico confronto

fine

Come puoi vedere non si va a ricerca, ma si trova esattamente ciò che si cerca.
Infatti "Ciao" si trova sicuramente nelle parole che iniziano per C, e già ne cassi un 90%.
Di questo 10% puoi togliere tutte quelle che non iniziano per ci... eccetera.
Sicuramente è più efficiente di confrontarle sempre tutte.

"Pseudo"codice:

unsigned int start = 0; 
unsigned int end = length of Dictionary;
unsigned int index = 0;

bool letterFound = false;

string myWord;
string word;

while( !wordFound )
{

    for(unsigned int i = start; i < end; i++)
    {
         word = Dictionnary[i];

//la prima volta che il carattere n della mia parola e' uguale al carattere n
//del dizionario, e' iniziato l'intervallo che ci interessa
         if(!letterFound && word[index] == myWord[index])
         {
              start = i;
              letterFound = true;
         }

//la prima volta che e' diversa dopo essere stata uguale, l'intervallo e' finito.
         if(letterFound && word[index] != myWord[index])
         {
              end = i;
              letterFound = false;
              index++;
              break;
         }
    }

    //se start ed end sono uno accanto all'altro, abbiamo trovato la parola.
    if(end == start+1)
         return Dictionary[start];
}

Ecco, dovrebbe funzionare
E' sempre piu' veloce di un algoritmo standard, in quanto non fa paragoni fra stringhe ma solo fra chars, e uno alla volta.
In piu', se la parola e' tipo abaco, fa 3 cicli e finisce.
Certo se e' ZUZZURELLONE ci mette cmq una svaria, anche se meno di altri algoritmi
Un'idea per migliorarlo è implementare un controllo "in avanti" e uno "all'indietro", in maniera da minimizzare lo spreco per le ultime lettere.

@Nico: guarda che 50.000 (numero medio di parole in un dizionario) char[20] occupano solamente 976kb... non credo ci sia alcun problema, Gears of War occupa 980 mb

[nico402]

Beh banale se il dizionario è ordinato alfabeticamente.

"ciao"

1 trovi c
2 in c trovi i
3 in i trovi a
4 in a trovi o
unico confronto

fine

Come puoi vedere non si va a ricerca, ma si trova esattamente ciò che si cerca.
Infatti "Ciao" si trova sicuramente nelle parole che iniziano per C, e già ne cassi un 90%.
Di questo 10% puoi togliere tutte quelle che non iniziano per ci... eccetera.
Sicuramente è più efficiente di confrontarle sempre tutte.

"Pseudo"codice:

unsigned int start = 0; 
unsigned int end = length of Dictionary;
unsigned int index = 0;

bool letterFound = false;

string myWord;
string word;

while( !wordFound )
{

    for(unsigned int i = start; i < end; i++)
    {
         word = Dictionnary[i];

//la prima volta che il carattere n della mia parola e' uguale al carattere n
//del dizionario, e' iniziato l'intervallo che ci interessa
         if(!letterFound && word[index] == myWord[index])
         {
              start = i;
              letterFound = true;
         }

//la prima volta che e' diversa dopo essere stata uguale, l'intervallo e' finito.
         if(letterFound && word[index] != myWord[index])
         {
              end = i;
              letterFound = false;
              index++;
              break;
         }
    }

    //se start ed end sono uno accanto all'altro, abbiamo trovato la parola.
    if(end == start+1)
         return Dictionary[start];
}

Ecco, dovrebbe funzionare
E' sempre piu' veloce di un algoritmo standard, in quanto non fa paragoni fra stringhe ma solo fra chars, e uno alla volta.
In piu', se la parola e' tipo abaco, fa 3 cicli e finisce.
Certo se e' ZUZZURELLONE ci mette cmq una svaria, anche se meno di altri algoritmi
Un'idea per migliorarlo è implementare un controllo "in avanti" e uno "all'indietro", in maniera da minimizzare lo spreco per le ultime lettere.

@Nico: guarda che 50.000 (numero medio di parole in un dizionario) char[20] occupano solamente 976kb... non credo ci sia alcun problema, Gears of War occupa 980 mb

avevo in mente dizionari giganteschi

non è che non abbia mai preso in mano un dizionario