PDA

Visualizza la versione completa : [C++] Mescolare in modo casuale e senza ripetizioni un array di char


mistergks
12-11-2011, 20:37
Mi serve una funzione per mescolare in modo casuale le lettere di una parola contenuta in un array di char.. Il problema è che non deve ripetere le stesse lettere, però in caso di ripetizione della parola stessa si!
ho provato a fare questo:



void permutaprima(char a[]){

int size=strlen(a);
int casuale=1+rand()%size;
for(int i=0; i<size;i++){
c[i]=a[casuale];
}

}



questo però mi genera numeri anche ripetuti!
spiego meglio cosa deve fare la funzione:
ad esempio se ho la parola casa deve mescolarmi le lettere senza ripetizioni: asca ad esempio..o csaa ecc...
con parole tipo farfalla deve fare la stessa cosa ma calcolando che ci sono due l

mistergks
13-11-2011, 00:49
Up

MItaly
13-11-2011, 01:07
http://en.wikipedia.org/wiki/Knuth_shuffle

ramy89
13-11-2011, 14:04
La mia idea è non di generare direttamente una permutazione della stringa, ma di prendere la stringa e di effettuare un certo numero di scambi dei suoi elementi.Il criterio con cui scambiarli è casuale.
Ho scritto una funzione:


void permutazione(char *s)
{
int i,min,random_1,random_2;
srand(time(NULL));
min=(strlen(s)-1)/2;
for(i=0;i<N;i++)
{
random_1=rand()%min;
random_2=rand()%min;
random_2+=min;
cswap(&s[random_1],&s[random_2]);
}
}

Dove N è una costante ed è il numero di scambi che si vuole effettuare.
cswap è una funzione per scambiare caratteri.
Per evitare che random_1 e random_2 abbiano gli stessi valori, ho fatto assumere a random_1 i valori che vanno da inizio stringa a metà stringa, e a random_2 i valori successivi, per poter generare una permutazione anche con un N molto piccolo.

ramy89
13-11-2011, 14:10
Mi sono dimenticato di dire che con questo criterio se la stringa ha cardinalità dispari, l' ultima lettera rimane sempre immutata.
Per cui in mezzo al ciclo bisogna aggiungere:


if(((strlen(s)-1)%2)==1)
random_2+=rand()%2;

mistergks
13-11-2011, 16:35
Originariamente inviato da ramy89
La mia idea è non di generare direttamente una permutazione della stringa, ma di prendere la stringa e di effettuare un certo numero di scambi dei suoi elementi.Il criterio con cui scambiarli è casuale.
Ho scritto una funzione:


void permutazione(char *s)
{
int i,min,random_1,random_2;
srand(time(NULL));
min=(strlen(s)-1)/2;
for(i=0;i<N;i++)
{
random_1=rand()%min;
random_2=rand()%min;
random_2+=min;
cswap(&s[random_1],&s[random_2]);
}
}

Dove N è una costante ed è il numero di scambi che si vuole effettuare.
cswap è una funzione per scambiare caratteri.
Per evitare che random_1 e random_2 abbiano gli stessi valori, ho fatto assumere a random_1 i valori che vanno da inizio stringa a metà stringa, e a random_2 i valori successivi, per poter generare una permutazione anche con un N molto piccolo.

ma cosi non capita che una lettera venga ripetuta? Com è la funzione cswap?

ramy89
13-11-2011, 16:41
Fa questo:

mescolare in modo casuale le lettere di una parola contenuta in un array di char
Se la parola è "ciaoc" una possibile permutazione è "ciaoc".
Non mi sembra ambigua la cosa.

La funzione cswap scambia caratteri, eccone un esempio:


void cswap(char *a, char *b)
{
char temp;
temp=*a;
*a=*b;
*b=temp;
}

Loading