Generare tutti i numeri random

[Eyescream]

Quale potrebbe essere il metodo più veloce per generare tutti i numeri da 1 a x ma in ordine casuale?

[kNemo]

In che linguaggio ???
se C

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *  Generazione di numeri Casuali Senza Ripetizioni	
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

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

#define MAX_NUM	90

int main () {
   int estratti [MAX_NUM];
   int numEstratto;
   int trovato;
   int i, j;

   srand(time(NULL));

	i = 0;
	do {
	    numEstratto = rand(MAX_NUM)+1;

	    /* Ricerca e confronto di numEstratti con gli Elementi Estratti */
	    trovato = 0;
            for (j=0; (j < i && !trovato); j++) {
      	        if (numEstratto == estratti[j]) {
          	    trovato = 1;
                }
            }

           /* Se l'Elemento non e' stato trovato incrementa i */
            if (!trovato) {
         	estratti[i] = numEstratto;
        	i++;
            }
         } while (i < MAX_NUM);

   /* Stampa dei numeri Estratti */
   for (i=0; i < MAX_NUM; i++) {
   	printf ("%d ", estratti[i]);
   }

   /* Ordinamento Vettore */
   for (i=0; i < MAX_NUM-1; i++) {
   	for (j=i; j < MAX_NUM; j++) {
      	    if (estratti[i] > estratti[j]) {
               int temp;
               temp = estratti[i];
               estratti[i] = estratti[j];
               estratti[j] = temp;
            }
	}
   }


   printf ("\n\n\t\t\t\t >> Estratti Ordinati << \n\n");
   /* Stampa dei numeri Estratti */
   for (i=0; i < MAX_NUM; i++) {
   	printf ("%-2d  ", estratti[i]);
   }

   getchar();
   return 0;
};

Questo e' un Programma che abbiamo fatto a scuola...
Estrae MAX_NUM numeri...
cmq e' facilmente modificabile per far estrarre n numeri...

Scusa per la formattazione ma que e' venuta da schifo...

[anx721]

Con quest'algoritmo puo darsi che si facciano un sacco di cicli prima di estrarre tutti i numeri, soprattutto quando sono rimasti pochi numeri da estrarre, e poi a rigor di logica non hai la certezza che tutti i numeri saranno effettivamente estratti. Tra l'altro il fatto di dover allocare tutti i numeri in un arrauy puo dare problemi di memoria se i numeri sono tanti.

Io opeterei per una lista linkata, quando estrai un numero i ti scorri la lista fino allo i-esimo elemento, lo togli dalla lista e, se MAX rappresenta il numero massimo da estrarre, decrementi MAX. Il generico elemento x coniene un numero oltre al link all'elemento successivo. Iniziaòlmente lo iesimo elemento contiene il numero i. Man mano che estrai numeri nella lista restano solo gli elementi non estratti, e ad ogni estrazioni non estrai il numero stesso, ma l'indice del prossimo elemento da considerare. In questo modo non fai piu di n estrazioni e la complessita totale è di n^2.

[internet]

Originariamente inviato da Eyescream
Quale potrebbe essere il metodo più veloce per generare tutti i numeri da 1 a x ma in ordine casuale?

se usi c++

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <ctime>

using namespace std;

const int MAX_NUM = 90;

struct RandGen {
  int operator () (int n) { return int(n * (rand()/(RAND_MAX+1.0))); }
};

int main()
{  
  int num[MAX_NUM], i, j;
  
  srand(time(NULL));

  for (i = 0; i < MAX_NUM; i++)
    num[i] = i+1;
  
  RandGen myrand;
  random_shuffle(num, num+MAX_NUM, myrand);
  
  for (i = 0; i < MAX_NUM; i += 5)
  {
    for (j = 0; j < 5; j++)
      cout << setw(3) << num[i+j] << ' ';

    cout << endl;
  }

  return 0;
}

random_shuffle è una funzione delle STL e ha complessità di tempo O(n).

[Eyescream]

Originariamente inviato da anx721
Con quest'algoritmo puo darsi che si facciano un sacco di cicli prima di estrarre tutti i numeri, soprattutto quando sono rimasti pochi numeri da estrarre, e poi a rigor di logica non hai la certezza che tutti i numeri saranno effettivamente estratti.

era esattamente questo il problema che mi stavo ponendo

[LeleFT]

Avevo già postato un algoritmo (in pseudo-codice) di complessità lineare... bastava usare la ricerca del forum: lo trovi QUI
Quell'algoritmo estraeva un mazzo di carte da 52 in modo casuale, quindi estraeva tutti i numeri da 1 a 52. Facendo variare il 52, invece di tenerlo fisso, si possono generare tutti i numeri da 1 a n.

Ciao.

[anx721]

Originariamente inviato da LeleFT
Avevo già postato un algoritmo (in pseudo-codice) di complessità lineare...

Il tuo algoritmo è di complessità quadratica :tongue: ed è la versione ad array di quello proposto da me con le liste :tongue:

[internet]

Originariamente inviato da Eyescream
Quale potrebbe essere il metodo più veloce per generare tutti i numeri da 1 a x ma in ordine casuale?

Che linguaggio stai usando?

[internet]

comunque la random_shuffle delle STL usa questo algoritmo

pseudocodice

FOR I = 1 TO N-1 DO
  R = numero a caso nell'intervallo [0, i]
  scambia v[I] <-> v[R]
END

in C

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


int my_random(int max)
{
  return (int)((rand()/(double)(RAND_MAX)) * max);
}

/* permuta in maniera casuale gli elementi dell'array <v>
   complessita' di tempo: THETA(n) */
void my_random_shuffle(int v[], int n)
{
  int i;

  for (i = 1; i < n; i++)
  {
    /* r numero a caso nell'intervallo [0, i] */
    int r = my_random(i);

    /* scambia: v[i] <-> v[r] */
    int t = v[i];
    v[i] = v[r];
    v[r] = t;
  }
}

#define MAX_NUM 90

int main()
{  
  int num[MAX_NUM], i, j;
  
  srand(time(NULL));

  for (i = 0; i < MAX_NUM; i++)
    num[i] = i+1;
  
  my_random_shuffle(num, MAX_NUM);
  
  for (i = 0; i < MAX_NUM; i += 5)
  {
    for (j = 0; j < 5; j++)
      printf("%3d ", num[i+j]);

    putchar('\n');
  }

  return 0;
}

Questo algoritmo ideato da D.Knuth, ha complessità di tempo lineare.

[ladyBlu]

ragazzi, prima di scrivere tonnellate di codice che potrebbe essere completamente inutile...
...sarebbe meglio che Eyescream specificasse il linguaggio che usa, cosa che doveva già fare nel titolo della discussione.