Generare 2 interi casuali...

[marcus81]

Come posso fare per generare 2 interi casuali da un insieme di interi da 1 a n, utilizzando la sola funzione rand ed evitando che il secondo numero sia uguale al primo?
Inoltre la probabilità deve essere uniforme per tutti i numeri, cioè la prima estrazione ho probabilità 1/n di beccare un elemento specifico, alla seconda estrazione tale probabilità è 1/n-1.
Grazie.

[cionci]

Prima estrai un numero da 1 a n e poi il secondo da 1 a n-1...se il secondo è maggiore o uguale al primo allora aggiungi 1...

[marcus81]

Thanks:)
Praticamente è come togliere l'elemento che è uscito alla prima estrazione...
e se invece volessi generare m numeri interi casuali diversi da un insieme n, con m<n, posso estendere tale procedimento?

[cionci]

Certo...ma è un po' più complesso...

Devi tenere un vettore ordinato di tutti gli interi usciti... Per ogni numero già estratto minore dell'intero estratto aumenti l'intero di 1 (ovviamente questa cosa deve essere dinamica, non puoi contare prima quanti sono e poi aumentare, perchè potresti trovarti a superare od uguagliare ancora un numero già estratto)...

C'è anche un altro modo, magari stilisticamente più bello, ma che probabilmente è più lungo dal punto di vista dell'esecuzione...

Continui ad estrarre ogni volta da una popolazione diminuita di 1... Crei un vettore con tutti gli elementi da estrarre (in questo caso i numeri da 1 a n)... Supponiamo che si chiami vett...
Se estraggo l'intero x da 1 a n-k l'elemento estratto sarà vett[x]... Vett[x] dovrà essere rimosso dal vettore ed il vettore dovrà essere compattato... Ad esempio questo procedimento in C++ si fa in due istruzioni ;)

[marcus81]

Il secondo metodo è semplicissimo da implementare anche in Matlab, anzi proprio con Matlab che è un linguaggio vettoriale dovrebbe essere molto veloce:)
Grazie;)

[cionci]

Se è Matlab direi proprio di sì ;)

[daryl74]

Non è per fare il pignolo ma sul primo consiglio dato da Cionci le probabilità sul secondo numero estratto non sono tutte uguali.

Dovendo scegliere un numero a caso fra 1 ed n.

-se alla prima estrazione è uscito m (con m<=n)
alla seconda estrazione la probabilità che esca il numero m+1 è maggiore (quasi doppia) poiche può uscire m (e quindi aggiungeresti 1 ottenendo m+1) oppure potrebbe uscire direttamente m+1. Quindi la probabilità è 1/n-1 + 1/n-1.

Sol 1: ridimensioni il vettore ed elimini gli elementi usciti.
Sol 2: (come nel secondo caso di Cionci) prendi un numero casuale fra n, n-1, n-2, elementi ipotetici di un vettore "indice"...

Esempio Pratico:
NumeroCasuale fra 1 ed 10 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

Soluzione 1: esce il 3 ridimensioni il vettore contenente valori in:
(1, 2, 4, 5, 6, 7, 8, 9, 10) e poi scegli un valore random fra 1 e 9 (elementi del vettore)

Soluzione 2: esce il 3, il tuo vettore rimane (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) poi scegli un numero fra 1 e 9. Se esce il 5 elemento corrisponde al numero 6 (cioè 5 più il conteggio dei numeri già estratti)
quindi i numeri successivi sono: nro uscito + conteggio dei numeri estratti in precedenza che sono minori o uguali al numero appena estratto. Cioè: se fosse uscito 2 non bisognava aggiungere 1.
Però la cosa mi sembra lunga da fare...

Non so se sono riuscito a spiegarmi...
Speriamo...

[marcus81]

Originariamente inviato da daryl74
-se alla prima estrazione è uscito m (con m<=n)
alla seconda estrazione la probabilità che esca il numero m+1 è maggiore (quasi doppia) poiche può uscire m (e quindi aggiungeresti 1 ottenendo m+1) oppure potrebbe uscire direttamente m+1. Quindi la probabilità è 1/n-1 + 1/n-1.


ma tu 1 lo aggiungi anche quando il secondo numero estratto è maggiore del primo numero estratto, non solo quando è uguale...
per i numeri da 1 a m-1 non ai problemi, da m a n è come se scavalcassi m aggiungendo appunto 1...
quindi se esce m diventa m+1
se esce m+1-->m+2...e così via
a me sembra corretto:confused:

[cionci]

Infatti aggiungendo nel caso che sia maggiore o uguale dovrebbe essere corretto...

[3nigma666]

/*funzione random ke genera un numerocasuale tra 0 e 1
quando poi viene riciamata la funzione il numeri viene moltipicato per una numero intero ke vuoi tu(ad esempio se vuoi ke il range dei numeri interi sia compreso tra 1 e 5000 moltiplichi per 5000)
Tu mi dirai ma un numerocompreso tra 0 e 1 moltiplicaot per un intero non mi restituisce un numero intero.Beh .. ke problema c'è basta fare un cast ,nel nostro caso da double passi a long (Se passi a int dovrebbe dare errore)
*/
#include <math.h>
#include <stdlib.h>
#include <iostream>
#include <stdio.h>

//NUMERI STATISTICAMENTE VALIDI
#define A 16087
#define M 2147483647
#define Q 127773
#define R 2836

double seed;
const int max = 2;
double vettore [max];

//FUNZIONE RANDOM
double Random()
{
double lo, hi, test;
hi = ceil(seed / Q);
lo = seed - Q * hi;
test = A * lo - R * hi;
if (test < 0.0) {
seed = test + M;
} else {
seed = test;
} /* endif */
return seed / M;
} //end random


void main (){
seed = 123456789; //il seme ,le cifre qua incluse vengono utilizzate nella generazione del numero casuale

for (int i=0; i<max;i++)
vettore[i] =(long)( Random()*5000);
for (int k=0; k<max;i++)
std::cout<<vettore[k]<<std::endl;
}

nel programma manca un controllo tale ke se un numero è uguale al precedente genera un nuovo numero,ma basta mettere un numero sufficientemente alto da moltiplicare per la funzione random ,scongiurando cosi ogni eventuale possibilta ke 2 numer isi ripetano (nell esempio ho messo 5000).Certo non è la sluzione migliore,posso buttare giu velocemente un abbozo di controllo:


....
bool diverso = false;
for (int i=0; i<max;i++){
vettore[i] =(long)( Random()*5000);
do{
if (vettore[i] == vettore[i-1])
vettore[i] =(long)( Random()*5000);
else
diverso = true;
}while (diverso != false);
.....


dovrebbe diventare cosi alla fine :


#include <math.h>
#include <stdlib.h>
#include <iostream>
#include <stdio.h>

//NUMERI STATISTICAMENTE VALIDI
#define A 16087
#define M 2147483647
#define Q 127773
#define R 2836

double seed;
const int max = 2;
double vettore [max];

//FUNZIONE RANDOM
double Random()
{
double lo, hi, test;
hi = ceil(seed / Q);
lo = seed - Q * hi;
test = A * lo - R * hi;
if (test < 0.0) {
seed = test + M;
} else {
seed = test;
} /* endif */
return seed / M;
} //end random


void main (){
seed = 123456789; //il seme ,le cifre qua incluse vengono utilizzate nella generazione del numero casuale

bool diverso = false;
for (int i=0; i<max;i++){
vettore[i] =(long)( Random()*5000);

do{
if (vettore[i] == vettore[i-1])
vettore[i] =(long)( Random()*5000);
else
diverso = true;
}while (diverso != true);

for (int k=0; k<max;i++)
std::cout<<vettore[k]<<std::endl;
}



spero ti sia utile.
non dovrebbe essere impossibile trasportarlo in matlab

3nigm@666 ;)

[cionci]

Ma a lui serviva in Matlab ;)

[marcus81]

Grazie ancora;)
Cmq secondo me il metodo più semplice e veloce di implementarlo in matlab è quello di togliere l'elemento e ricompattare il vettore, proprio per la innata predisposizione di matlab a lavorare con le matrici.

[3nigma666]

lo so ke gli serviva in matlab,ma trasportarlo in matlab nn deve essere un granke difficile.... io purtroppo il matlab nn lo conosco cosi bene, l' ho usato solo una volta per un progetto di un esame e mi faceva parecchio skifo come linguaggio.. (questo non vuol dire ke non lo ritenga utile)

[daryl74]

Senza fare caso a quello che ho scritto (alla fine la mia soluzione numero 2 era identica a quella proposta da Cionci e che avevo criticato [maggiore o uguale --> aggiungi 1])...
In ogni caso sono convinto che la soluzione più semplice sia:
Sol 1: ridimensioni il vettore ed elimini gli elementi usciti. che poi è la conclusione a cui è arrivato anche Marcus
Cmq secondo me il metodo più semplice e veloce di implementarlo in matlab è quello di togliere l'elemento e ricompattare il vettore, proprio per la innata predisposizione di matlab a lavorare con le matrici.Scusa Cionci per la critica immotivata...

Ciao

[marcus81]

Ottimo, se ci sono altri spunti ben vengano!
Qualcuno conosce qualche altro metodo ancora più ottimizzato in matlab?