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

[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

[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;
}

[anx721]

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

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