Newsgroup: it.scienza.informatica
Titolo: Generazione numeri casuali

Forse pongo un problema banale, ma qualcuno può comunque darmi qualche
dritta per una soluzione?
Devo inserire `N' interi, tutti diversi tra loro, in un vettore di
dimensione 'N-1'; gli interi sono generati pseudo-casualmente ad esempio
mediante rand() in C.
La funzione rand() genera il numero e verifica se è già stato estratto
(cioè se è già presente nel vettore): in caso affermativo (intero già
estratto) ripete l'estrazione, in caso negativo (intero non ancora
estratto) lo inserisce nel vettore (ad esempio il valore `x' viene
inserito in corrispondenza dell'indice `x-1') e procede con una nuova
estrazione. 
Questo ciclo si ripete fino al completamento del vettore (quindi finche
sono stati estratti ed inseriti tutti gli `N' valori).
Problema:
- quando sono stati estratti pochi interi rispetto ad `N', la probabilità
che l'intero generato casualmente non sia ancora stato estratto è elevata.
- quando gran parte degli `N' valori sono stati estratti, la probabilità
che ad ogni estrazione, il valore sia già stato estratto, è molto alta. In
questo caso ne consegue che l'estrazione, e le relative verifiche per
controllare che l'intero non sia ancora presente nel vettore, si ripetono,
allungando enormemente i tempi di esecuzione del programma.
Se N=1000, dopo che sono stati inseriti 999 interi nel vettore,
nell'attesa che venga estratto l'unico intero mancante--io divento vecchio
(probabilità di estrarre il numero mancante, ad ogni chiamata rand(), è
teoricamente 1/1000 se non sbaglio).
Sembra banale me se N è grande i tempi di esecuzione di un simile
programmino in C sono lunghissimi. Come posso risolvere il problema? Cioè
come posso comprimere i tempi visto che per riempire un vettore di 10
elementi impiego circa 30 secondi?
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 estrazione. 
// non testato:
const int N=1000;
int v[N];
void fun() {
   // riempio il vettore con numeri progressivi
   for (int i=0; i<N; i++)
     v[i]=i;
   // faccio N estrazioni
   for (int i=0;i<N; i++) {
     // gli elementi v[0],...,v[i-1] contengono i primi numeri estratti
     // gli elementi v[i],...,v[N-1] contengono i numeri rimasti
     int n=i+rand()%(N-i); // numero casuale tra i e (N-1);
     int x=v[n];  // numero da inserire nel vettore, tra quelli rimasti
     // aggiorna la lista dei numeri rimasti:
     // al posto di x ci metto v[i]
     v[n]=v[i];
 
     // si è liberato il posto, memorizzo l'estratto
     v[i]=x;
   }
}
E.

 mediante rand() in C.
Come fai a mettere N interi in un vettore di dimensione N-1?
Comunque ti conviene usare l'algoritmo di Fisher-Yates:
http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
Considera in ogni caso che la rand() del C in genere ha una pessima
distribuzione ed è anche lenta, meglio usare il mersenne twister:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
anche incluso nella Gnu Scientific Library: 
http://www.gnu.org/software/gsl/
Se hai bisogno di una distribuzione di probablità particolarmente
buona fai attenzione a come inizializzi il generatore (non usare
l'orologio) e a non usare il resto della divisione intera per ridurre
i valori generati in un intervallo prestabilito.

 }
Sbaglio o il codice di cui sopra non tiene conto dei numeri già estratti?
int n=i+rand()%(N-i); // numero casuale tra i e (N-1);
Con l'istruzione di cui sopra si restringe l'intervallo di partenza in cui
estrarre il casuale, ma non si tiene conto del fatto che un intero già
estratto è all'interno di tale intervallo (tutti gli interi estratti
ndevono infatti essere differenti). Come escludi i casuali già estratti?
Forse però mi sfugge qualcosa...
E' evidente che N interi non possono stare in un vettore di N-1 elementi!
Nulla da eccepire a tal proposito!


jacopoxxx ha scritto:
 > Forse pongo un problema banale, ma qualcuno può comunque darmi qualche
 > dritta per una soluzione?
 >
 > Devo inserire `N' interi, tutti diversi tra loro, in un vettore di
 > dimensione 'N-1'; gli interi sono generati pseudo-casualmente
 > ad esempio mediante rand() in C.
Se usi il linguaggio C++, puoi sfruttare l'algoritmo random_shuffle 
facente parte della libreria standard:
#include <algorithm>
#include <iostream>
int main() {
     const int n_items = 1000;
     int a[n_items];
     for (int i = 0; i < n_items; ++i) a[i] = i;
     std::random_shuffle(a, a + n_items);
     std::copy(a, a + n_items,
         std::ostream_iterator<int>(std::cout, ", "));
}
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

 estrazione.
Puoi risolvere il problema usando due vettori:
v1[N] contiene inizialmente i numeri da 0 a N-1
v2[N] e` il vettore obiettivo
for ( i = 0; i != N; v1[i] = i++ );
for ( i = 0; i != N; i++ ) {
  x = < random [0..N) >;
  while ( v1[x] == -1 ) x = (x+1) % N;
  v2[i] = v1[x];
  v1[x] = -1;
}
Ciao,
  -- Roberto


"n" non è il valore che inserisci nel vettore, ma l'indice da cui
prendere tale valore per scambiarlo con il valore all'indice corrente
"i". Poichè tutte le operazioni sul vettore sono degli scambi, i
valori rimangono sempre gli stessi, ne viene cambiato l'ordine ma non
vengono ne duplicati ne eliminati.
Comunque considera che usare il resto della divisione intera per
restringere l'intervallo dei numeri casuali introduce un bias: anche
se la rand() estraesse valori da una distribuzione casuale uniforme
indipendente, prendendo il resto della divisione intera (per qualunque
divisore che non sia una potenza di due) i valori più bassi hanno
ciascuno una probabilità di essere estratti più doppia rispetto ai
valori più alti.
Ad esempio, se vuoi estrarre un valore da 0 a 5 (diciamo per simulare
un tiro di dado) usando rand() % 6 ottieni i valori 0 ed 1 ciascuno
con probabilità 1/4 ed i restanti valori ciascuno con probabilità 1/8.
Inoltre, le funzioni rand() standard di molti linguaggi sono basate su
algoritmi detti generatore lineari congruenziali (
http://en.wikipedia.org/wiki/Linear_congruential_generator
 ).
Questi algoritmi hanno in genere distribuzioni particolarmente cattive
soprattutto nei bit meno significativi, che sono proprio quelli
selezionati dall'operazione %, causando bias ancora più evidenti.
In particolare, con molti di questi generatori usando rand() % 2 si
ottiene una sequenza di 0 e 1 perfettamente alternati.
Per ottenere buoni numeri casuali in un intervallo [0..N-1] conviene:
- Usare un buon generatore.
- Trovare il più piccolo M tale che N <= M ed M sia una potenza di
due. Estrarre x = rand() % M (che non introduce bias e si può anche
ottimizzare usando il bitwise and). Se x < N restituire x, altrimenti
ripetere.
<snip>