Algoritmo per l'estrazione di n numeri casuali

Tweet

Questo post nasce a seguito di una breve discussione intercorsa con il mio caro amico Mario Monfrecola che mi chiedeva, a titolo d'esercizio, di trovare un algoritmo per la generazione di n numeri casuali interi distinti, tutti compresi nell'intervallo [1, n].

La soluzione che ho immaginato è quella che vado a descrivere nel seguito e che ho pensato, avendo sempre a mente un uso parsimonioso della memoria, di realizzare utilizzando un unico array, di lunghezza n, che alla fine dell'elaborazione conterrà la sequenza dei numeri estratti.

Innanzitutto, viene inizializzato un array con la successione di tutti i numeri da 1 a n.

Poi, viene eseguito un ciclo di n passi in cui, ad ogni passo p, viene generato un numero casuale intero compreso tra 1 e n - p + 1, l'elemento dell'array che si trova in corrispondenza di tale numero viene aggiunto in coda all'array e poi dallo stesso array viene rimosso l'elemento che si trova nella posizione del numero casuale generato.

Per chiarire meglio quanto detto, vediamo un esempio concreto in cui, per semplicità, consideriamo il caso n = 5.

Allora, inizialmente l'array viene inizializzato nel seguente modo:

[1, 2, 3, 4, 5]

Passo 1

Il numero estratto ha un valore compreso tra 1 e 5.

Supponiamo che tale valore sia 5.

Allora il numero che si trova in posizione 5 viene aggiunto in coda all'array: [1, 2, 3, 4, 5, 5] e dall'array viene rimosso l'elemento che si trova in quinta posizione; per cui esso resta invariato:

[1, 2, 3, 4, 5]

Passo 2

Il numero estratto ha un valore compreso tra 1 e 4.

Supponiamo che tale valore sia 1.

Allora il numero che si trova in posizione 1 viene aggiunto in coda all'array: [1, 2, 3, 4, 5, 1] e dall'array viene rimosso l'elemento che si trova in prima posizione; per cui esso diventa:

[2, 3, 4, 5, 1]

Passo 3

Il numero estratto ha un valore compreso tra 1 e 3.

Supponiamo che tale valore sia 2.

Allora il numero che si trova in posizione 2 viene aggiunto in coda all'array: [2, 3, 4, 5, 1, 3] e dall'array viene rimosso l'elemento che si trova in seconda posizione; per cui esso diventa:

[2, 4, 5, 1, 3]

Passo 4

Il numero estratto ha un valore compreso tra 1 e 2.

Supponiamo che tale valore sia 2.

Allora il numero che si trova in posizione 2 viene aggiunto in coda all'array: [2, 4, 5, 1, 3, 4] e dall'array viene rimosso l'elemento che si trova in quinta posizione; per cui esso diventa:

[2, 5, 1, 3, 4]

Passo 5

Il numero estratto ha un valore compreso tra 1 e 1.

Quindi, all'ultimo passo, tale valore è necessariamente 1.

Allora il numero che si trova in posizione 1 viene aggiunto in coda all'array: [2, 5, 1, 3, 4, 2] e dall'array viene rimosso l'elemento che si trova in quinta posizione; per cui esso diventa:

[5, 1, 3, 4, 2]

Da quanto visto, ci rendiamo anche conto del fatto che l'ultimo passo può essere evitato in quanto il numero generato non è casuale ma vale sempre 1 e ha il solo effetto di spostare il primo elemento dell'array in coda allo stesso ma poiché per noi non è importante la sua posizione, possiamo anche saltare tale passo limitando il ciclo fino al passo n-1; per cui, nel caso visto sopra, l'array dell'estrazione sarà quello del passo 4: [2, 5, 1, 3, 4].

Come visto, l'algoritmo è estremamente semplice e la sua implementazione in un linguaggio di programmazione ad alto livello è pressoché immediata.

A titolo d'esempio, ne propongo una in Java:

// Impostare n con un opportuno valore
final int n = 90;
ArrayList a = new ArrayList(n + 1);
Random random = new Random();
for (int i = 0; i < n; i++)
a.add(i, i + 1);
for (int i = 0; i < n - 1; i++) {
int j = random.nextInt(n - i) + 1;
a.add(a.get(j - 1));
a.remove(j - 1);
}
System.out.println(a);