Genera un numero univoco all’interno dell’intervallo (0 – X), mantenendo una cronologia per evitare duplicati

Mi sono imbattuto nella sfida in cui ho bisogno di una funzione che restituisca un numero casuale all’interno di un determinato intervallo da 0 - X Non solo, ma richiedo che il numero restituito sia unico ; non duplicare i numeri che sono già stati restituiti nelle chiamate precedenti alla funzione.

Opzionalmente, quando ciò è fatto (ad esempio, l’intervallo è stato “esaurito”), è sufficiente restituire un numero casuale all’interno dell’intervallo.

Come si potrebbe fare questo?

Hai una buona risposta di programmazione. Eccone uno con un touch più teorico per completare il tuo panorama 🙂

Il tuo problema si chiama “sampling” o “subset sampling” e ci sono diversi modi per farlo. Sia N la gamma che stai campionando (cioè, N=X+1 ) e M la dimensione del tuo campione (il numero di elementi che vuoi scegliere).

  • se N è molto più grande di M , ti consigliamo di usare un algoritmo come quello suggerito da Bentley e Floyd nella sua rubrica ” Programming Pearls: a sample of brilliance ” (temporaneamente disponibile senza la schermata di blocco di ACM qui ), consiglio vivamente questo dato che esplicitamente danno il codice e discutono in termini di tabelle hash, ecc .; ci sono alcuni trucchetti

  • se N è all’interno dello stesso range di M , allora potresti voler usare il rimescolamento di Fisher-Yates ma fermarti dopo solo M passi (invece di N )

  • se non lo sai, l’algoritmo a pagina 647 del libro di Devroye sulla generazione casuale è piuttosto veloce .

Questo dovrebbe farlo:

 function makeRandomRange(x) { var used = new Array(x), exhausted = false; return function getRandom() { var random = Math.floor(Math.random() * x); if (exhausted) { return random; } else { for (var i=0; i 

Uso:

 var generate = makeRandomRange(20); var x1 = generate(), x2 = generate(), ... 

Sebbene funzioni, non ha buone prestazioni quando viene generato il casuale x-esimo - cerca l'intera lista per un posto libero. Questo algoritmo , un rimescolamento di Fisher-Yates passo a passo, dalla domanda Numeri univoci (non ripetuti) in O (1)? , si esibirà meglio:

 function makeRandomRange(x) { var range = new Array(x), pointer = x; return function getRandom() { pointer = (pointer-1+x) % x; var random = Math.floor(Math.random() * pointer); var num = (random in range) ? range[random] : random; range[random] = (pointer in range) ? range[pointer] : pointer; return range[pointer] = num; }; } 

( Demo su jsfiddle.net )

Versione estesa che genera solo un "gruppo" di numeri univoci:

 function makeRandomRange(x) { var range = new Array(x), pointer = x; return function getRandom() { if (range) { pointer--; var random = Math.floor(Math.random() * pointer); var num = (random in range) ? range[random] : random; range[random] = (pointer in range) ? range[pointer] : pointer; range[pointer] = num; if (pointer < = 0) { // first x numbers had been unique range = null; // free memory; } return num; } else { return Math.floor(Math.random() * x); } }; } 

( Demo )

Ho scritto questa funzione. Mantiene il proprio array con una cronologia di numeri generati, evitando i duplicati iniziali, continuando a generare un numero casuale se tutti i numeri nell’intervallo sono stati emessi una volta:

 // Generates a unique number from a range // keeps track of generated numbers in a history array // if all numbers in the range have been returned once, keep outputting random numbers within the range var UniqueRandom = { NumHistory: new Array(), generate: function(maxNum) { var current = Math.round(Math.random()*(maxNum-1)); if (maxNum > 1 && this.NumHistory.length > 0) { if (this.NumHistory.length != maxNum) { while($.inArray(current, this.NumHistory) != -1) { current = Math.round(Math.random()*(maxNum-1)); } this.NumHistory.push(current); return current; } else { //unique numbers done, continue outputting random numbers, or we could reset the history array (NumHistory = [];) return current; } } else { //first time only this.NumHistory.push(current); return current; } } }; 

Ecco un Fiddle funzionante

Spero che questo sia utile a qualcuno!

Modifica: come sottolineato da Pointy di seguito, potrebbe rallentare con un intervallo ampio (qui è un violino, che va oltre un intervallo da 0-1000 , che sembra funzionare bene). Però; Non avevo bisogno di una gamma molto ampia, quindi forse questa funzione non è adatta se cerchi di generare e tenere traccia di una vasta gamma.

Puoi provare a generare il numero usando il valore di data e ora corrente che lo renderebbe univoco. Per renderlo all’interno dell’intervallo, potrebbe essere necessario utilizzare alcune funzioni matematiche.