[C] Vettori Simili

[lucas87]

2 Vettori A e B di lunghezza n e m, si dicono simili se hanno gli stessi elementi.

esempi:
1- A=1,2,3 B=1,3,2 SIMILI
2- A=1,2,3 B=1,1,2,3 SIMILI
3- A=1,2,3 B=1,2,3,4 NON SIMILI

L'ultimo caso mi crea difficoltà...forse dovrei verificare prima gli elementi di A per quelli di B...poi se m>n controllo gli elementi in piu di B con quelli di A.

Che dite andrà??

[andbin]

2 Vettori A e B di lunghezza n e m, si dicono simili se hanno gli stessi elementi.

esempi:
1- A=1,2,3 B=1,3,2 SIMILI
2- A=1,2,3 B=1,1,2,3 SIMILI
3- A=1,2,3 B=1,2,3,4 NON SIMILI

L'ultimo caso mi crea difficoltà...forse dovrei verificare prima gli elementi di A per quelli di B...poi se m>n controllo gli elementi in piu di B con quelli di A.

Che dite andrà??Se n'era già parlato in <questo> (http://www.hwupgrade.it/forum/showthread.php?t=1322787) thread (è un po' lungo e complesso, non so se ti può essere utile).

Comunque faccio un piccolo riassunto: due array sono simili solo se contengono gli stessi elementi, in qualunque posizione. Per risolvere la questione, giriamo la cosa al negativo: non sono simili se uno dei due array contiene anche solo un elemento che non c'è nell'altro.

Ed è questa la chiave della soluzione. In sostanza vuol dire che devi suddividere la elaborazione in due grossi step: verifica di a contro b e poi viceversa verifica di b contro a. Se trovi un elemento che non c'è nell'altro, allora non sono simili.

[lucas87]

Grazie...avevo infatti pensato di fare cosi...ma poi ho pensato che doveva esserci un modo per non usare 4 cicli. A quanto pare no...ok ti ringrazio.

[lucas87]

Se a qualcuno interessa posto la soluzione.


int simili(int *v,int *w,int dim1, int dim2){
int i,j;
int cnt=0;
for (i=0;i<dim1;i++){
for (j=0;j<dim2;j++){
if (v[i]==w[j]){
cnt++;
break;
}
}
}
if(cnt!=dim1) return 0;
cnt=0;

for (j=0;j<dim2;j++){
for (i=0;i<dim1;i++){
if (w[j]==v[i]){
cnt++;
break;
}
}
}
if(cnt!=dim2) return 0;

return 1;
}

[lucas87]

Che poi scusa un attimo andbin, ma quello delle permutazioni era una cazzata, non bastava ordinare i 2 vettori e verificare che erano identici spiccicati??

[lucas87]

Posto anche quello delle permutazioni...magari c'è casec87 in ascolto.



#include <stdio.h>
#include <stdlib.h>

int perm(int *v,int *w,int dim);
void ordinamento(int *t,int dim);
void swap(int *p,int *q);


int main(void){
int v[]={1,1,3};
int w[]={3,3,1};


ordinamento(v,3);
ordinamento(w,3);


printf("%d",perm(v,w,3));


system("PAUSE");
return 0;

}

void ordinamento(int *t,int dim){
int i,j;
for (i=0;i<dim;i++){
for (j=dim-1;j>i;j--){
if (t[j-1]>t[j]) swap(&t[j-1],&t[j]);
}
}
}

void swap(int *p,int *q){
int aux;
aux=*p;
*p=*q;
*q=aux;
}

int perm(int *v,int *w,int dim){
int i,j;
for (i=0,j=0;i<dim;i++,j++)

if (v[i]!=w[j]) return 0;

return 1;
}

[andbin]

Che poi scusa un attimo andbin, ma quello delle permutazioni era una cazzata, non bastava ordinare i 2 vettori e verificare che erano identici spiccicati??Nel caso i due array differiscano nel numero di ripetizioni di certi valori, anche ordinandoli non ottieni due array esattamente identici.

[lucas87]

Appunto per quello....se differiscono di numero di ripetizioni non sono uno permutazione dell'altro quindi return 0, altrimenti se andando a confrontare in parallelo gli elementi dell'uno e dell'altro e ognuno corrisponde all'altro return 1.

[andbin]

Appunto per quello....se differiscono di numero di ripetizioni non sono uno permutazione dell'altro quindi return 0, altrimenti se andando a confrontare in parallelo gli elementi dell'uno e dell'altro e ognuno corrisponde all'altro return 1.Allora non sarebbe più come hai detto all'inizio: A=1,2,3 B=1,1,2,3 SIMILI

[lucas87]

nn dicevo quello dei simi...ho detto simili per dire identici...errore mio...se vedi la soluzione infatti vedi che confronto in parallelo e non per pogni elemento di A scorro il vettore B