verifica anagramma e permutazione casuale

[mistergks]

Mi sono imbattuto in questo programma:
Si scriva in C++ un programma completo opportunamente modularizzato in funzioni che, lette da input due parole di uguale lunghezza, verifichi se sono l’una anagramma dell’altra. Due parole sono una l’anagramma dell’altra se contengono le stesse lettere ma in ordine diverso. Esempio: La parola locandiera è un anagramma della parola calendario.
Se le due parole non sono una l’anagramma dell’altra, si consideri la prima inserita da input e se ne costruisca un anagramma permutando in modo casuale le lettere di cui è composta (non importa se la parola ottenuta non è di senso compiuto). Esempio: se da input sono state inserite le parole casa e sala, si consideri la parola casa e si permutino in modo casuale le sue lettere. Dopo questo procedimento si potrebbe ad esempio ottenere la parola asca.

Ho provato a farlo, ma ho un problema in fase di esecuzione: mi fa inserire la prima parola e mi esce un messaggio di errore che il programma ha smesso di funzionare. Qual'è il problema? Grazie mille.

il mio codice:

#include <iostream>
using namespace std;

void alfasort(char x[]);//ordina alfabeticamente
bool verificaAnagramma(char *a, char *b);//verifica se due parola in ordine alfabetico sono uguali e quindi anagrammi
void permutaprima(char *a, char *c);//permuta in modo casuale le lettere della parola a e memorizza in c

int main(){
char *a, *b, *c;
cout<<"a"<<endl; cin>>a;
cout<<"b"<<endl; cin>>b;

alfasort(a);//ordina la stringa a in ordine alfabetico
alfasort(b);//ordina la stringa b in ordine alfabetico

if(!verificaAnagramma(a,b)){//se non sono uno l'anagramma dell'altro
cout<<"non sono anagrammi quindi permuto";
permutaprima(a,c); //permuta la stringa a in un nuovo array c
}
else{
cout<<"OK SONO ANAGRAMMI"<<endl;
}


system("pause");
return 0;
}

void alfasort(char x[]){
for(int i=0; i<strlen(x);i++){
if(x[i+1]<x[i])
x[i]=x[i+1];
}
}


bool verificaAnagramma(char *a, char *b){

for(int i=0; i<strlen(a);i++){
if(a[i]!=b[i])
return false;
}
return true;
}

void permutaprima(char *a, char *c){
int size=strlen(a);
for(int i=0; i<size;i++){
c[i]=a[size-i];
c[i+2]=a[i];
}
}

[starfred]

Ok, ho letto il tuo codice, ho aspettato 10 minuti prima di rispondere, ora sono calmo... :D

La mia non vuol essere una polemica ma il codice che hai appena scritto (ammesso che l'hai scritto te e che non hai fatto copy/paste da altri codici) mostra una totale carenza di fondamenti di base.

Il mio consiglio è quello di prendere il libro e di iniziare a leggerlo dall'inizio concentrandoti sul concetto di puntatori/riferimenti/indirizzi/stringhe etc. etc.

[clockover]

alfasort non può funzionare... non è un algoritmo di ordinamento funzionante... da uno sguardo qui http://it.wikipedia.org/wiki/Algoritmo_di_ordinamento e scegline uno semplice tipo insertion sort, bubble sort , ecc... semplice mi raccomando...
per permutare una parola il discorso è relativamente semplice... una parola al contrario va bene lo stesso, ma una parola con le sue lettere prese a casaccio è molto più figa :D comunque per adesso aggiusta alfasort e come funzione di permutazione fai la parola al contrario... quando hai aggiustato almeno queste cose parliamo del resto..

Ora la parte più brutta.... non puoi pretendere di assegnare una parola sana ad un indirizzo di memoria senza prima aver riservato la memoria...
char *t è un indirizzo e hai allocato spazio per un solo byte
char t[10] oppure char *t = malloc(10); anche qui hai in t un indirizzo di memoria, ma hai anche riservato spazio per 10 bytes

poi più in avanti capirai anche qual'è la differenza tra i due tipi di allocazioni

[mistergks]

alfasort non può funzionare... non è un algoritmo di ordinamento funzionante... da uno sguardo qui http://it.wikipedia.org/wiki/Algoritmo_di_ordinamento e scegline uno semplice tipo insertion sort, bubble sort , ecc... semplice mi raccomando...
per permutare una parola il discorso è relativamente semplice... una parola al contrario va bene lo stesso, ma una parola con le sue lettere prese a casaccio è molto più figa :D comunque per adesso aggiusta alfasort e come funzione di permutazione fai la parola al contrario... quando hai aggiustato almeno queste cose parliamo del resto..

Ora la parte più brutta.... non puoi pretendere di assegnare una parola sana ad un indirizzo di memoria senza prima aver riservato la memoria...
char *t è un indirizzo e hai allocato spazio per un solo byte
char t[10] oppure char *t = malloc(10); anche qui hai in t un indirizzo di memoria, ma hai anche riservato spazio per 10 bytes

poi più in avanti capirai anche qual'è la differenza tra i due tipi di allocazioni

Grazie per la risposta. Per quanto riguarda l'inizializzazione di un char pensavo si potesse fare col puntatore.. quindi inizializzo come array di char[] e poi posso utilizzarlo col puntatore senza fare ulteriori assegnamenti? cioè :

char stringa[10];
//e poi la utilizzo cosi:
if(*stringa.....ecc..



Invece per l'ordinamento alfabetico:
pensavo che i char potessero essere trattati come gli int!
cioè 'a'>'b' sarebbe come dire che a sia maggiore di b in base all'alfabeto e quindi restituisce true..o sbaglio??
Potrei risolvere allora con la funzione strcmp(s1,s2)?? però ora che ci penso...a me servirebbe controllare lettere della stessa parola e non due parole..quindi come uso la strcmp!?

per la permutazione casuale:
Avevo pensato di farlo con la funzione rand della libreria <cstdlib> ma non sono riuscito;
come posso farlo? idee, indizi?

[clockover]

1) non hai allocato spazio per il tuo array di char
2) puoi ordinare i char come gli int, ma quell'algoritmo non è un algoritmo di ordinamento, quindi non ordina -- hai letto la pagina di wikipedia che ti ho likato?
3) puoi fare una permutazione casuale, ma devi tenere conto dei caratteri che hai già utilizzato... se il tuo rand ti da 2 volte il valore 2 per permutare la parola "casa" avrai 2 's' nella parola permutata, il che non va bene. Quindi devi escogitare un altro metodo per poter fare una permutazione casuale.

Per ora fai come ti ho già detto, cioè prendi la parola al contrario perchè hai altri problemi ben più gravi da risolvere (te lo ha già detto anche starfred)

[mistergks]

1) non hai allocato spazio per il tuo array di char
2) puoi ordinare i char come gli int, ma quell'algoritmo non è un algoritmo di ordinamento, quindi non ordina -- hai letto la pagina di wikipedia che ti ho likato?
3) puoi fare una permutazione casuale, ma devi tenere conto dei caratteri che hai già utilizzato... se il tuo rand ti da 2 volte il valore 2 per permutare la parola "casa" avrai 2 's' nella parola permutata, il che non va bene. Quindi devi escogitare un altro metodo per poter fare una permutazione casuale.

Per ora fai come ti ho già detto, cioè prendi la parola al contrario perchè hai altri problemi ben più gravi da risolvere (te lo ha già detto anche starfred)

ho modificato la funzione di ordinamento:

void alfasort(char x[]){
char temp;
for(int i=0; i<strlen(x);i++){
if(x[i]>x[i+1])
temp=x[i];
x[i]=x[i+1];
x[i+1]=temp;
}
}

ora com'è?


gli array di char li alloco cosi e li inizializzo da input..può andare?:
char a[20], b[20], c[20];
cout<<"a"<<endl; cin>>a;
cout<<"b"<<endl; cin>>b;

[clockover]

ho modificato la funzione di ordinamento:

void alfasort(char x[]){
char temp;
for(int i=0; i<strlen(x);i++){
if(x[i]>x[i+1])
temp=x[i];
x[i]=x[i+1];
x[i+1]=temp;
}
}

ora com'è?


e secondo te funziona? L'hai provato?

[mistergks]

e secondo te funziona? L'hai provato?

No non mi funziona. Ho provato a capire il perchè e sono arrivato alla conclusione che la funzione essendo void, non restituisce il vettore ordinato.. quindi dovrei restituirlo? come?:muro:

[clockover]

Io invece sono arrivato alla conclusione che il link di wikipedia che ti ho dato non l'hai proprio visto

[mistergks]

Io invece sono arrivato alla conclusione che il link di wikipedia che ti ho dato non l'hai proprio visto

certo che l'ho visto! da li ho preso il bubble sort...ma proprio non riesco a capire qual'è il problema...avevo provato a inserire un ciclo in piu di for, ma niente ugualmente. la funzione mi da una sola lettera. Perché? Potresti spiegarmelo? Ci sto impazzendo!:confused:

[gugoXX]

certo che l'ho visto! da li ho preso il bubble sort...ma proprio non riesco a capire qual'è il problema...

Prendi una decina di carte da scala 40, mescolale e mettile sul tavolo in fila.
Poi fai finta di essere il computer e prova ad applicare l'algoritmo da te scritto.
Quando arrivi alla fine forse capirai cosa dovrai fare per aggiustarlo.
O per riscriverne un altro.
In questo modo imparerai dai tuoi stessi errori, che e' un ottimo approccio.

[mistergks]

Risolto:

void alfasort(char x[]){
char temp;
for(int pass=1; pass<strlen(x);pass++)
for(int i=0; i<strlen(x)-1;i++){
if(x[i]>x[i+1]){
temp=x[i];
x[i]=x[i+1];
x[i+1]=temp;
}//if
}//for
}


Ho aggiunto un altro ciclo for perchè non mi ero accorto che con uno solo si faceva una sola passata.. e ho messo la lunghezza della stringa -1 perchè altrimenti x+1 va fuori..
ora mi funziona..
Passiamo agli altri errori del programma??
Ho provato a compilare il nuovo codice ed eseguire: il programma mi verifica gli anagrammi e mi permuta anche se le due parole sono anagrammi...come mai?

[!fazz]

per me sbagli completamente approccio: fai prima a contare il numero di volte che trovi ogni singolo carattere

è un esercizio quindi tieni le cose più semplici possibili senza puntatori ecc ecc gioca solo con la tabella ascii

crea 2 vettori statico di 25 interi (lettere A-Z)
inizializzalo a zero

per ogni carattere della parola
{
consideralo come un numero intero
se il numero è >96 (lettera minuscola) sottrai 32 (lo trasformi in lettera maiuscola)
incrementa di uno il vettore alla posizione [carattere-65]
}

fai lo stesso per il secondo vettore

confronta se i 2 vettori sono uguali, alla prima differenza non è un anagramma

una cosa del genere



void contacaratteri (int v[], char s[])
{

int len, num;
for(int c=0;c<25;c++)
{
v[c]=0;
}
len= strlen(s);
for(int c=0;c<len;c++)
{
num= (int) s[c];
if (num >96)
num-=32;
v[num-65]++;

}
}


bool controllaanagramma( char s1[], char s2[])
{
int v1[25], v2[25];
contacaratteri (v1, s1);
contacaratteri (v2, s2);

for (int c=0; c<25; c++)
{
if (v1[c]!=v2[c])
return false;
}
return true

}

scritto così di botto potrebbero esserci degli errori ma il principio è chiaro

[mistergks]

Ho compilato e quindi messo un pò in ordine il tuo codice anche per eventuali altri lettori interessati alla questione:


#include <iostream>
using namespace std;

bool controllaanagramma( char s1[], char s2[]);
void contacaratteri (int v[], char s[]);

int main(){
int v[]={0};
char s1[]={"ciao"};
char s2[]={"locandiera"};
if(controllaanagramma(s1,s2))
cout<<" ok"<<endl;
else
cout<<"no"<<endl;

system("pause");
return 0;
}

void contacaratteri (int v[], char s[])
{

int len, num;
for(int c=0;c<25;c++)
{
v[c]=0;
}
len= strlen(s);
for(int c=0;c<len;c++)
{
num= (int) s[c];
if (num >96)
num-=32;
v[num-65]++;

}
}


bool controllaanagramma( char s1[], char s2[])
{
int v1[25], v2[25];
contacaratteri (v1, s1);
contacaratteri (v2, s2);

for (int c=0; c<25; c++)
{
if (v1[c]!=v2[c])
return false;
}
return true;

}


che dire... pare funzioni(anche il mio funzionava!! il problema è nella permutazione!)
Però il tuo algoritmo mi sembra molto laborioso! io mica me le ricordo tutte quelle cifre ascii! come fai a trovarle? 96, 32, 65 ecc...

[clockover]

Infatti secondo me era meglio che continuavi con il tuo di metodo... almeno sapevi cosa stavi facendo.. poi ragionavi anche su quello suggerito da !fazz

[clockover]

Dai uno sguardo a questo algoritmo per l'ordinamento e vedi che differenze ci sono con il tuo
void sort(char *str){
int i = 0, j = 0;
int len = -1;
size(str, len);
printf("%s --> size = %d\n", str, len);
for(i = 0; i < len; i++){
for(j = i + 1; j < len; j++){
if(str[i] > str[j])
swap(str, i, j);
}
}
printf("%s --> size = %d\n", str, len);
}

ignora le chiamate size e swap che sono delle macro che ho definito io in precedenza.
size conta le lettere che sono contenute nella parola e swap invece scambia semplicemente due elementi nella parola

edit
ricorda che questo è il peggior algoritmo di ordinamento, ma nel tuo caso va bene lo stesso

[mistergks]

Infatti secondo me era meglio che continuavi con il tuo di metodo... almeno sapevi cosa stavi facendo.. poi ragionavi anche su quello suggerito da !fazz

Infatti ho continuato! Per la verifica degli anagrammi siamo apposto! Il problema ora sta nella permutazione! non mi stampa niente..dovrebbe permutare la stringa a nell'array di char c e stamparlo.




#include <iostream>
using namespace std;

void alfasort(char x[]);//ordina alfabeticamente
bool verificaAnagramma(char *a, char *b);//verifica se due parole in ordine alfabetico sono uguali e quindi anagrammi
void permutaprima(char *a, char *c);//permuta in modo casuale le lettere della parola a e memorizza in c

int main(){
char a[20], b[20], c[20];
cout<<"a"<<endl; cin>>a;
cout<<"b"<<endl; cin>>b;

alfasort(a);//ordina la stringa a in ordine alfabetico
alfasort(b);//ordina la stringa b in ordine alfabetico

if(!(verificaAnagramma(a,b))){//se non sono uno l'anagramma dell'altro
cout<<"non sono anagrammi quindi permuto";
permutaprima(a,c); //permuta la stringa a in un nuovo array c
cout<<c;
}else
cout<<"OK SONO ANAGRAMMI"<<endl;


system("pause");
return 0;
}

void alfasort(char x[]){
char temp;
for(int pass=1; pass<strlen(x);pass++)
for(int i=0; i<strlen(x)-1;i++){
if(x[i]>x[i+1]){
temp=x[i];
x[i]=x[i+1];
x[i+1]=temp;
}//if
}//for
}


bool verificaAnagramma(char *a, char *b){
alfasort(a);
alfasort(b);
for(int i=0; i<strlen(a);i++){
if(a[i]!=b[i])
return false;
}
return true;
}

void permutaprima(char *a, char *c){
int size=strlen(a);
for(int i=0; i<size-2;i++){
c[i]=a[size-i];
c[i+2]=a[i];
}
}

[!fazz]

Ho compilato e quindi messo un pò in ordine il tuo codice anche per eventuali altri lettori interessati alla questione:


#include <iostream>
using namespace std;

bool controllaanagramma( char s1[], char s2[]);
void contacaratteri (int v[], char s[]);

int main(){
int v[]={0};
char s1[]={"ciao"};
char s2[]={"locandiera"};
if(controllaanagramma(s1,s2))
cout<<" ok"<<endl;
else
cout<<"no"<<endl;

system("pause");
return 0;
}

void contacaratteri (int v[], char s[])
{

int len, num;
for(int c=0;c<25;c++)
{
v[c]=0;
}
len= strlen(s);
for(int c=0;c<len;c++)
{
num= (int) s[c];
if (num >96)
num-=32;
v[num-65]++;

}
}


bool controllaanagramma( char s1[], char s2[])
{
int v1[25], v2[25];
contacaratteri (v1, s1);
contacaratteri (v2, s2);

for (int c=0; c<25; c++)
{
if (v1[c]!=v2[c])
return false;
}
return true;

}


che dire... pare funzioni(anche il mio funzionava!! il problema è nella permutazione!)
Però il tuo algoritmo mi sembra molto laborioso! io mica me le ricordo tutte quelle cifre ascii! come fai a trovarle? 96, 32, 65 ecc...


per la questione della tabella ascii, a parte che una sottomano serve sempre

comunque basta ricordarsi che
A è 65
a è 97
e il 32 non è altro che la differenza


per la laboriosità mi sembra molto più laborioso il tuo metodo tra ordinamenti e confronti vari oltre che computazionalmente parlando senza senso: consumi una cifra di tempo di calcolo tra (inutili )ordinamenti ecc ecc dimenticantoti della definizione di anagramma

una stringa è un anagramma di un altra se e solo contiene ogni carattere ripetuto lo stesso numero di volte

se non ti è chiaro fatto con i numeri avresti potuto farlo con un case switch sul carattere ma sicuramente è più giusto che fare il casino che stai facendo
tra ordinamenti e permutazioni varie il tuo algoritmo ha complessità troppo elevata

ricorda sempre una delle regole principe della programmazione: il KISS



riguardo alle permutazioni: devi rifare tutta la funzione visto che di casuale non hai nulla devi usare il random

[mistergks]

ho capito il tuo codice..magari sarà pure piu efficiente...ma a me per il momento non interessa la complessita dell'algoritmo :D.. devo preparare un esame di fondamenti!
In ogni caso...ho imparato una cosa nuova! :D quindi grazie.

Per quanto riguarda la permutazione quindi non va proprio bene quello che ho scritto? ora provo a fare qualcosa col rand..

[__ZERO_UNO__]

ho capito il tuo codice..magari sarà pure piu efficiente...ma a me per il momento non interessa la complessita dell'algoritmo :D.. devo preparare un esame di fondamenti!
In ogni caso...ho imparato una cosa nuova! :D quindi grazie.

Per quanto riguarda la permutazione quindi non va proprio bene quello che ho scritto? ora provo a fare qualcosa col rand..

Per la permutazione potresti usare questo algoritmo:
ammesso che v sia l'array di caratteri o una stringa

// sono suff. length(v) - 1 scambi. Il primo elem. di v ha indice 1
for k = length(v) downto 2 do
// numero casuale in [0,1] o (0,1), è lo stesso.
u = rand();
// indice casuale in {1,...,k}.
// Attenzione, Int sta per parte intera, non arrotondamento.
i = Int(u*k) + 1;
// scambia l'elem in posizione i con quello in pos k
swap(v[i], v[k]);
end

[WarDuck]

per la questione della tabella ascii, a parte che una sottomano serve sempre

comunque basta ricordarsi che
A è 65
a è 97
e il 32 non è altro che la differenza


per la laboriosità mi sembra molto più laborioso il tuo metodo tra ordinamenti e confronti vari oltre che computazionalmente parlando senza senso: consumi una cifra di tempo di calcolo tra (inutili )ordinamenti ecc ecc dimenticantoti della definizione di anagramma

una stringa è un anagramma di un altra se e solo contiene ogni carattere ripetuto lo stesso numero di volte

se non ti è chiaro fatto con i numeri avresti potuto farlo con un case switch sul carattere ma sicuramente è più giusto che fare il casino che stai facendo
tra ordinamenti e permutazioni varie il tuo algoritmo ha complessità troppo elevata

ricorda sempre una delle regole principe della programmazione: il KISS



riguardo alle permutazioni: devi rifare tutta la funzione visto che di casuale non hai nulla devi usare il random

Non sono d'accordo, il ragazzo deve risolvere il problema prima di tutto, ed ha perfettamente senso ordinare le due stringhe per verificare se sono anagrammi, dal momento che in un'anagramma è proprio la posizione a fare la differenza.

ordinato -> adinoort
tanordio -> adinoort

Quindi le due parole sono anagrammi.

In realtà se ci pensi bene quello che proponi tu non è nient'altro che un ordinamento Integer Sort O(n) applicato ai caratteri (che sono sempre interi dal nostro punto di vista) :D.

Notare anche che per piccoli numeri un ordinamento O(n^2) si comporta meglio di altri e che comunque su piccoli set di dati la differenza è trascurabile.

Ogni algoritmo va applicato in base anche al contesto e non solo perché sulla carta è più efficiente...

[mistergks]

Per la permutazione potresti usare questo algoritmo:
ammesso che v sia l'array di caratteri o una stringa

// sono suff. length(v) - 1 scambi. Il primo elem. di v ha indice 1
for k = length(v) downto 2 do
// numero casuale in [0,1] o (0,1), è lo stesso.
u = rand();
// indice casuale in {1,...,k}.
// Attenzione, Int sta per parte intera, non arrotondamento.
i = Int(u*k) + 1;
// scambia l'elem in posizione i con quello in pos k
swap(v[i], v[k]);
end



non ho ben capito...potresti mostrarmi codice c++?o magari c..

[__ZERO_UNO__]

Ti ho scritto lo pseudo-codice per non darti la pappa pronta e imparare a farlo da solo.Non capisco come del codice in c++ possa essere più chiaro dello pseudo-codice.Se non hai capito qualcosa in particolare chiedilo.
Comunque... Abbiamo n posizione nell'array. Parto dal fondo, cioè da n, e scelgo in modo casuale quale lettera mettere in n. Ogni lettera della parola ha uguale probabilità di occupare quella posizione. Dopo devo scegliere una lettera, fra quelle che sono rimaste, da mettere nella posizione n-1. Fatto questo devo scegliere una lettera, fra quelle rimaste, da mettere nella posizione n-2. Si prosegue cosi fino all'esaurimento delle lettere.
k è la posizione corrente in cui devo mettere la lettera e, l'insieme {1, 2, ..., k} di indici, le posizioni delle lettere possibili da scegliere.




u = rand();
i = Int(u*k) + 1;

è un modo per generare una variabile aleatoria con distribuzione discreta uniforme su k elementi.