Permutazioni Casuali

[supertonno]

Ciao a tutti.
Avrei bisogno di aiuto nel creare delle permuazioni casuali di numeri da 1 a N.
Per esempio 4 permutazioni a caso di una serie di numeri da 1 a 10.
Qualcuno ha in mente come fare senza generarle tutte e po prenderle a caso?

Grazie:)

[cionci]

Linguaggio ?

[supertonno]

va benissimo C o C++

[cionci]

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


/* estrazione senza reimbussolamento di m elementi
su una popolazione di n elementi */
int vettore_casuale(int *v, int m, int n)
{
char *v2;
int i, j;
if(m > n)
return 1;
v2 = malloc(sizeof(char)*n);
memset(v2, 0, sizeof(char)*n);
for(i=0; i<m; i++)
{
v[i] = rand()%(n-i) + 1;
j = 0;
while(v[i] > 0 )
{
if(v2[j++] == 0)
v[i]--;
}
v2[j-1] = 1;
v[i] = j;
}
free(v2);
return 0;
}

#define M 10
#define N 10

int main()
{
int v[M], i;
srand((unsigned)time(NULL));

vettore_casuale(v, M, N);
for(i=0; i<M; ++i)
printf("%4d", v[i]);
printf("\n");
vettore_casuale(v, M, N);
for(i=0; i<M; ++i)
printf("%4d", v[i]);
printf("\n");
vettore_casuale(v, M, N);
for(i=0; i<M; ++i)
printf("%4d", v[i]);
printf("\n");
getchar();
return 0;
}

[supertonno]

Grazie Mille, ora lo provo:D

[anx721]

Questa è l'implementazione di un noto algoritmo, inventato da non ricordo chi, per generare una permutazione di n elementi con complessità lineare:


#include <stdlib.h>


void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}


int * perm(unsigned int n){
int *vect = (int *)malloc(n * sizeof(int));
int i;
for(i = 0; i < n; i++)
vect[i] = i;
for (i = n-1;i >= 0;i--)
swap(&vect[i],&vect[(int) ((rand()/(1.0 + RAND_MAX)) * (i+1))]);
return vect;
}

[supertonno]

Originariamente inviato da anx721

#include <stdlib.h>


void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}


int * perm(unsigned int n){
int *vect = (int *)malloc(n * sizeof(int));
int i;
for(i = 0; i < n; i++)
vect[i] = i;
for (i = n-1;i >= 0;i--)
swap(&vect[i],&vect[(int) ((rand()/(1.0 + RAND_MAX)) * (i+1))]);
return vect;
}




Lo stavo proprio implementando cosi, con swap casuali...
Ora li provo tutte e due vedo quello che ha prestazioni migliori:D

[anx721]

la "mia" credo sia piu efficiente

[atidem]

Originariamente inviato da anx721
Questa è l'implementazione di un noto algoritmo, inventato da non ricordo chi, per generare una permutazione di n elementi con complessità lineare:


#include <stdlib.h>


void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}


int * perm(unsigned int n){
int *vect = (int *)malloc(n * sizeof(int));
int i;
for(i = 0; i < n; i++)
vect[i] = i;
for (i = n-1;i >= 0;i--)
swap(&vect[i],&vect[(int) ((rand()/(1.0 + RAND_MAX)) * (i+1))]);
return vect;
}




Standard shuffling algorithm
Seminumerical Algorithms (Vol. 2 of "The Art of Computer Programming")



for (i=0; i<N; i++)
a[i] = i;
for (j=N-1; j>0; j--) {
i = choose(0,j); /* Generatore di numeri casuale */
t = a[i];
a[i] = a[j];
a[j] = t;
}


:D

[anx721]

Originariamente inviato da atidem
Standard shuffling algorithm
Seminumerical Algorithms (Vol. 2 of "The Art of Computer Programming")

:D

ok, ma se non ricordo l'ha inventato un pezzo grosso tipo knut o qualkunaltro...

[atidem]

Originariamente inviato da anx721
ok, ma se non ricordo l'ha inventato un pezzo grosso tipo knut o qualkunaltro...

Knuth
http://www-cs-faculty.stanford.edu/~knuth/index.html

[cionci]

Originariamente inviato da anx721
la "mia" credo sia piu efficiente
Decisamente...anche perchè quello sopra era fatto per risolvere altri problemi...