Genera numeri casuali nella matrice

Possibile duplicato:
Numeri casuali univoci in O (1)?

Sono nuovo in Java. Voglio generare un insieme di numeri casuali da un dato set e anche i numeri non devono ripetersi. Ad esempio, i numeri possibili sono [0,1,2,3] , voglio ottenere tre numeri univoci casuali memorizzati in una matrice. Ex. [0,2,1], [2,3,1], [0,3,2] ecc.

Hai bisogno di un rimescolamento di Fisher-Yates.

Questa è una soluzione “select n from m” molto efficiente che ti dà un sottoinsieme dei tuoi valori con zero possibilità di duplicati (e nessun ordinamento up-front non necessario). Lo pseudo-codice per fare ciò segue:

 dim n[N] // gives n[0] through n[N-1] for each i in 0..N-1: n[i] = i // initialise them to their indexes nsize = N // starting pool size do N times: i = rnd(nsize) // give a number between 0 and nsize-1 print n[i] nsize = nsize - 1 // these two lines effectively remove the used number n[i] = n[nsize] 

Selezionando semplicemente un numero casuale dal pool (in base alla dimensione attuale del pool), sostituendolo con il numero superiore di quel pool, quindi riducendo la dimensione del pool, si ottiene un shuffle senza doversi preoccupare di un numero elevato di swap in anticipo.

Questo è importante se il numero è alto in quanto non introduce un ritardo di avvio non necessario.

Ad esempio, esamina il seguente bench-check, scegliendo 10 da 10:

 <------ n[] ------> 0 1 2 3 4 5 6 7 8 9 nsize rnd(nsize) output ------------------- ----- ---------- ------ 0 1 2 3 4 5 6 7 8 9 10 4 4 0 1 2 3 9 5 6 7 8 9 7 7 0 1 2 3 9 5 6 8 8 2 2 0 1 8 3 9 5 6 7 6 6 0 1 8 3 9 5 6 0 0 5 1 8 3 9 5 2 8 5 1 9 3 4 1 1 5 3 9 3 0 5 9 3 2 1 3 9 1 0 9 

Puoi vedere la piscina che si riduce man mano che vai e, poiché sostituisci sempre quella usata con quella inutilizzata, non avrai mai una ripetizione.


Ecco un piccolo programma Java che mostra questo in azione:

 import java.util.Random; public class testprog { private int[] pool; // The pool of numbers. private int size; // The current "size". private Random rnd; // A random number generator. // Constructor: just initilise the pool. public testprog (int sz) { pool = new int[sz]; size = sz; rnd = new Random(); for (int i = 0; i < size; i++) pool[i] = i; } // Get next random number in pool (or -1 if exhausted). public int next() { if (size < 1) return -1; int idx = rnd.nextInt(size--); int rval = pool[idx]; pool[idx] = pool[size]; return rval; } // Test program for the pool. public static void main(String[] args) { testprog tp = new testprog (10); for (int i = 0; i < 11; i++) System.out.println (tp.next()); } } 

L'output è (per una corsa particolare):

 3 5 1 0 6 4 9 2 8 7 -1 

Il -1 è lì solo per mostrarti cosa succede quando esaurisci la lista. Dato che hai dichiarato esplicitamente che non vuoi duplicati, restituisce un valore sentinella. Potresti anche scegliere altre opzioni come lanciare un'eccezione o semplicemente riavviare il pool.