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...

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 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]

Originariamente inviato da 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 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]

Originariamente inviato da 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)

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]

Originariamente inviato da mistergks

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]

Originariamente inviato da clockover

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?

[clockover]

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

[mistergks]

Originariamente inviato da clockover

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!

[gugoXX]

Originariamente inviato da mistergks

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]

Originariamente inviato da 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

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]

Originariamente inviato da 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...

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 .. devo preparare un esame di fondamenti!
In ogni caso...ho imparato una cosa nuova! 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__]

Originariamente inviato da mistergks

ho capito il tuo codice..magari sarà pure piu efficiente...ma a me per il momento non interessa la complessita dell'algoritmo .. devo preparare un esame di fondamenti!
In ogni caso...ho imparato una cosa nuova! 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