Calcolo random numeri senza ripetizioni

[cecce88]

raga devo fare un programma ke calcoli i 20 numeri random da 1 a 100 senza ripetizioni!
Questo è il programma che ho fatto per calcolare 20 numeri random CON RIPETIZIONE!

[i]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{ int i,v[20],j;
printf("Benvenuti nel programma che calcola numeri casuali da 1 a 20 senza ripetizioni");
srand(time(NULL));
for (i=0;i<20;i++)
{ v[i]=rand()%100+1;
printf(" %d",v);

}
system("PAUSE");
return 0;
}


vorrei sapere come fare per controllare il vettore ?? devo fare un altro ciclo?Mi sapreste spiegare il vostro ragionamento e non darmi solo la soluzione?
Vi ringrazio in anticipo x l'aiuto!

[andbin]

Originariamente inviato da cecce88

raga devo fare un programma ke calcoli i 20 numeri random da 1 a 100 senza ripetizioni!

Parlando in generale un modo semplice è tramite il seguente algoritmo:

Si crea un array con tutti i numeri possibili per la estrazione. Si estrae un numero che fa da indice nell'array, si prende l'elemento dall'array e l'ultimo elemento lo si sposta in questa posizione. La dimensione "logica" dell'array si "accorcia" e si ripete dalla estrazione dell'indice.

Ok, forse a parole non è molto chiaro:

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Si estrae un indice tra 0 e 9 compresi, esempio 4. Il primo valore estratto è 5.
Si sposta l'ultimo elemento e si "accorcia" logicamente la dimensione dell'array.

{ 1, 2, 3, 4, 10, 6, 7, 8, 9, 10 }

Si estrae un indice tra 0 e 8 compresi, e si va avanti così.

[jappilas]

oppure, potresti adottare un array di flag booleane relative allo stato ( usato in precedenza o meno) di ogni valore del range - soluzione concettualmente semplice e dalla ridotta complessità computazionale, qui applicabile trattandosi di un range limitato di valori interi
riprendendo il tuo codice, aggiunte evidenziate in blu

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

int main()
{   
    int i, j, temp, v[20];
    boolean used[100];
    printf("Benvenuti nel programma che calcola numeri casuali da 1 a 20 senza ripetizioni");
    srand(time(NULL));

    for (j=0;j<100;j++)
    {
         used[j]=false;
    }

    for (i=0;i<20;i++)
    {
        do
        { 
            temp = rand()%100+1;   
        }while (used[temp] == true) ;
        
        used[temp] = true;     
        v[i] = temp;                                                          
        printf(" %d",v[i]);                      
    }
    system("PAUSE");
    return 0;
}

[nuovoUtente86]

Non so se la STL di c++ preveda dei metodi che inserito un valore segnala la sua presenza o meno in una lista tipo il metodo contains delle liste in java.
Cmq il ragionamento è semplice:dopo ogni estrazione verifichi che il numero non sia presente nei precedenti
int[20] numeri;
int posizione=0;
for(int i=0;i<20;i++){bool inserito=false;
while(!inserito){
numero_estratto=rand()%100+1; bool presente=false;
for(int j=0;j<posizione;j++){
if(numeri[j]==numero_estratto)presente=true;}
if(!presente){numeri[posizione]=numero_estratto;
posizione++;inserito=true;}}

[cionci]

Io farei così:

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

#define POPOLAZIONE	100

int main()
{
	int i, j;
	int estratti[20];
	char giaEstratti[POPOLAZIONE];

	/* azzero gli elementi del vettore */
	memset(giaEstratti, 0, sizeof(giaEstratti));

	/* inizializzo il generatore di numeri casuali */
	srand((unsigned)time(NULL));

	for(i = 0; i < 20; ++i)
	{
	    /* estraggo un numero */
	    estratti[i] = rand() % (POPOLAZIONE  -  i) + 1;

	    /* lo aggiorno incrementandolo di uno per ogni 
	    numero precedentemente estratto minore di lui */
	    for(j = 0; j < estratti[i]; ++j)
	    { 
	        if(giaEstratti[j])
	        {
	            estratti[i]++;
	        }
	    }
	    giaEstratti[estratti[i] - 1] = 1;
	    printf("%d ", estratti[i]);
	}
	return 0; 
}

Per mantenere una distribuzione delle probabilità di estrazione coerente bisogna fare solo 20 estrazioni. Infatti quando in un'urna ci sono 100 palline e ne tiro fuori una dentro ne rimangono 99. Così ho diminuito la dimensione della popolazione.
Questa diminuzione porta all'estrazione di numeri in un campo di valori più ristretto, per riadeguarlo devo aggiungere un 1 al numero estratto per ogni numero precedentemente estratto minore del numero estratto.
Faccio un esempio con 5 palline per farti capire. Nella prima riga c'è la numerazione delle palline (prima seconda terza quarta etc), nella seconda il numero scritto sulla pallina.

12345
12345

estraggo la 2a pallina e rimangono:

1234
1345

estraggo la 3a...quindi per scoprire il numero che c'è scritto sopra devo aggiungere 1 per ottenere il numero scritto sulla pallina.

123
135

estraggo la 3a...quindi aggiungo 1 perché la 2 è già estratta. Mi diventa 4a, la 4 è già stata estratta e quindi aggiungo 1 ed ottengo la 5

In pratica quello che vado ad estrarre con la rand è la i-esima posizione libera nel vettore dei numeri già estratti.

Da notare che ripetendo l'estrazione senza diminuire la popolazione non avrei rispettato la distribuzione di probabilità.

[altairz]

sei sicuro che con questo metodo la probabilità di estrarre un numero non dipenda dall'estrazione dei numeri precedenti?

Come statistico conosco alcuni algoritmi per estrarre un campione casuale semplice (cioè esattamente la richiesta di cecce88). Purtroppo non sò dirvi la loro complessità magari possono tornare utili. La probabilità di estrarre un intero è sempre la stessa ed i numeri estratti sono tutti distinti (quindi senza ripetizione)

Primo:

a. Generare n numeri pseudo-casuali con distribuzione uniforme in [0, 1]
b. Moltiplicare gli n numeri generati per N
c. Arrotondare per eccesso gli n numeri ottenuti; si hanno così n numeri interi, ciascuno compreso tra 1 ed N
d. Se gli n numeri ottenuti sono tutti differenti, l'algoritmo si ferma. Se invece sono solo k < n gli interi distinti ottenuti, bisogna eliminare gli n - k duplicati, e ripetere la procedura generando questa volta n - k interi. Di nuovo, si hanno in totale n numeri interi. Se sono tutti distinti l'algoritmo si ferma, mentre in caso contrario bisogna eliminare i duplicati e ripetere ancora la procedura, fino ad ottenere n interi distinti.

Secondo:

0)
Definire N quantità B1, B2, ..., Bn e inizializzarle a 0
Inizializzare una variabile k = 0

1) Generare un numero pseudo-casuale U con distribuzione uniforme in [0, 1]
2) Se U = 1, tornare al passo 1, altrimenti andare a 3.
3) Determinare l'intero j tale che j/N <= U < (j+1)/N, con j = 0, 1, ..., N-1
4) Se Bj = 0 allora metterlo uguale ad 1 quindi k = k+1 e andare al passo 5
5) Se k = n allora si ferma l'algoritmo, altrimenti tornare al passo 1

[cionci]

A me sembra che lui chiedesse una estrazione senza reinbussolamento...e di conseguenza ad ogni estrazione la popolazione diminuisce di 1. E di conseguenza varia anche la probabilità di estrazione di ogni elemento.
Ovviamente già fare rand()%X inserisce un errore in quanto di solito RAND_MAX non è multiplo di X, ma questo è un altro paio di maniche

[altairz]

Originariamente inviato da cionci

A me sembra che lui chiedesse una estrazione senza reinbussolamento...e di conseguenza ad ogni estrazione la popolazione diminuisce di 1. E di conseguenza varia anche la probabilità di estrazione di ogni elemento.
Ovviamente già fare rand()%X inserisce un errore in quanto di solito RAND_MAX non è multiplo di X, ma questo è un altro paio di maniche

se è un'estrazione in blocco allora cambia tutto dal primo esempio che lui ha postato sembrava che li estraesse ogni volta dalla medesima "popolazione" di partenza

[cionci]

Originariamente inviato da altairz

se è un'estrazione in blocco allora cambia tutto dal primo esempio che lui ha postato sembrava che li estraesse ogni volta dalla medesima "popolazione" di partenza

Infatti lui ha definito ciò che sapeva fare come estrazione con ripetizione, ma a lui interessava senza ripetizione

[altairz]

Originariamente inviato da cionci

Infatti lui ha definito ciò che sapeva fare come estrazione con ripetizione, ma a lui interessava senza ripetizione

beh, allora a questo punto dipende da quello di cui ha bisogno

Anche gli algoritmi che ho postato poco fa danno come risultato n numeri casuali senza ripetizione. L'unica differenza è la probabilità di estrazione. Nel mio caso tutti i numeri hanno la stessa probabilità, indipendente dalle estrazioni già avvenute, a differenza invece dell'estrazione "senza reinserimento nell'urna"

[cionci]

Sì, sono equiprobabili, ma in teoria potresti generare un'attesa attiva
Ad esempio: estrai 100000 numeri senza ripetizione da una popolazione di 100000. Secondo me ci mette anche diversi secondi