Il modo più efficiente di scegliere casualmente un insieme di interi distinti

Sto cercando l’algoritmo più efficiente per scegliere casualmente un insieme di n interi distinti, in cui tutti gli interi sono in un intervallo [0..maxValue].

vincoli:

  • maxValue è maggiore di n e probabilmente molto più grande
  • Non mi interessa se l’elenco di output è ordinato o meno
  • tutti gli interi devono essere scelti con uguale probabilità

La mia idea iniziale era di build un elenco di interi [0..maxValue], quindi estrarre n elementi a caso senza sostituzione. Ma sembra abbastanza inefficiente, specialmente se maxValue è grande.

Qualche soluzione migliore?

Per piccoli valori di maxValue tali che è ragionevole generare una matrice di tutti gli interi in memoria, è ansible utilizzare una variazione del rimescolamento di Fisher-Yates, tranne che per eseguire solo i primi n passaggi.


Se n è molto più piccolo di maxValue e non desideri generare l’intero array, puoi utilizzare questo algoritmo:

  1. Mantieni una lista ordinata di numeri selezionati finora, inizialmente vuota.
  2. Scegli un numero casuale x tra 0 e maxValue – (elementi in l )
  3. Per ogni numero in l se è minore o uguale a x , aggiungi 1 a x
  4. Aggiungi il valore corretto di x nell’elenco ordinato e ripeti.

Se n è molto vicino a maxValue allora puoi scegliere a caso gli elementi che non sono nel risultato e poi trovare il complemento di quel set.


Ecco un altro algoritmo che è più semplice ma ha un tempo di esecuzione potenzialmente illimitato:

  1. Mantieni un set di elementi selezionati finora, inizialmente vuoto.
  2. Scegli un numero a caso tra 0 e maxValue .
  3. Se il numero non è in s , aggiungilo a s .
  4. Torna al punto 2 finché s ha n elementi.

In pratica se n è piccolo e maxValue è grande questo sarà abbastanza buono per la maggior parte degli scopi.

Ecco un algoritmo ottimale, supponendo che siamo autorizzati a utilizzare le hashmap. Funziona in tempo O (n) e spazio (e non tempo O (maxValue), che è troppo costoso).

È basato sull’algoritmo di campionamento casuale di Floyd. Vedi il mio post sul blog per i dettagli. Il codice è in Java:

 private static Random rnd = new Random(); public static Set randomSample(int max, int n) { HashSet res = new HashSet(n); int count = max + 1; for (int i = count - n; i < count; i++) { Integer item = rnd.nextInt(i + 1); if (res.contains(item)) res.add(i); else res.add(item); } return res; } 

Un modo per farlo senza generare l’intero array.

Diciamo che voglio un sottoinsieme selezionato casualmente di m elementi da un set {x1, …, xn} dove m <= n.

Considera l’elemento x1. Aggiungo x1 al mio sottoinsieme con probabilità m / n.

  • Se aggiungo x1 al mio sottoinsieme, riduco il mio problema a selezionare (m – 1) elementi da {x2, …, xn}.
  • Se non aggiungo x1 al mio sottoinsieme, riduco il mio problema alla selezione di m articoli da {x2, …, xn}.

Mescolare, sciacquare e ripetere fino a m = 0.

Questo algoritmo è O (n) dove n è il numero di elementi che devo considerare.

Immagino piuttosto che ci sia un algoritmo O (m) in cui ad ogni passo consideri quanti elementi rimuovere dal “fronte” del set di possibilità, ma non mi sono convinto di una buona soluzione e devo fare qualche lavora ora!

Se stai selezionando M elementi da N , la strategia cambia a seconda che M sia dello stesso ordine di N o molto meno (cioè meno di circa N / log N).

Se hanno dimensioni simili, passano attraverso ogni articolo da 1 a N Tieni traccia di quanti oggetti hai finora (chiamiamoli m oggetti scelti da n che hai passato), e poi prendi il prossimo numero con probabilità (Mm)/(Nn) e scartalo altrimenti. Quindi aggiorna n opportunamente e continua. Questo è un algoritmo O(N) a basso costo costante.

Se, d’altra parte, M è significativamente inferiore a N , allora una strategia di ricampionamento è buona. Qui dovrai ordinare M modo che tu possa trovarli rapidamente (e questo ti costerà del tempo O(M log M) – incollarli in un albero, per esempio). Ora scegli i numeri in modo uniforms da 1 a N e inseriscili nella tua lista. Se trovi una collisione, riprova. Scontrerai per il M/N del tempo (in realtà, stai integrando da 1 / N a M / N), che richiederà di riprenderti (in modo ricorsivo), quindi ti aspetteresti di prendere M/(1-M/N) selezioni per completare il processo. Pertanto, il costo per questo algoritmo è di circa O(M*(N/(NM))*log(M)) .

Questi sono entrambi metodi semplici che puoi semplicemente implementare entrambi, assumendo che tu abbia accesso ad un albero ordinato, e scegliere quello che è appropriato dato la frazione di numeri che saranno scelti.

(Si noti che i numeri di selezione sono simmetrici rispetto a non selezionarli, quindi se M è quasi uguale a N , allora è ansible utilizzare la strategia di ricampionamento, ma scegliere quei numeri da non includere: questa può essere una vittoria, anche se si deve spingere tutto quasi- N numeri intorno, se la generazione del numero casuale è costosa.)

La mia soluzione è la stessa di Mark Byers ‘. Ci vuole O (n ^ 2) tempo, quindi è utile quando n è molto più piccolo di maxValue. Ecco l’implementazione in python:

 def pick(n, maxValue): chosen = [] for i in range(n): r = random.randint(0, maxValue - i) for e in chosen: if e <= r: r += 1 else: break; bisect.insort(chosen, r) return chosen 

Il trucco è usare una variazione di shuffle o, in altre parole, una mescolanza parziale.

 function random_pick( a, n ) { N = len(a); n = min(n, N); picked = array_fill(0, n, 0); backup = array_fill(0, n, 0); // partially shuffle the array, and generate unbiased selection simultaneously // this is a variation on fisher-yates-knuth shuffle for (i=0; i=0; i--) // O(n) times { selected = backup[ i ]; value = a[ N ]; a[ N ] = a[ selected ]; a[ selected ] = value; N++; } return picked; } 

NOTA l’algoritmo è rigorosamente O(n) sia nel tempo che nello spazio , produce selezioni imparziali (è un rimescolamento parziali imparziale ) e non ha bisogno di hasmap (che potrebbero non essere disponibili e / o di solito hide una complessità dietro la loro implementazione, es. il tempo non è O(1) , potrebbe anche essere O(n) nel peggiore dei casi)

adattato da qui

Generatore congruenziale lineare modulo maxValue + 1. Sono sicuro di aver già scritto questa risposta, ma non riesco a trovarlo …

AGGIORNAMENTO: ho torto. L’output di questo non è uniformsmente distribuito. Dettagli sul perché sono qui .


Penso che questo algoritmo qui sotto sia ottimale . Ad esempio, non è ansible ottenere prestazioni migliori di questo.

Per la scelta di n numeri su m numeri, l’algoritmo migliore offerto finora è presentato di seguito. La sua peggiore complessità del tempo di esecuzione è O (n) e richiede solo un singolo array per memorizzare i numeri originali. Mescola parzialmente i primi n elementi dall’array originale, quindi scegli i primi n numeri mescolati come soluzione.

Questo è anche un programma C pienamente funzionante. Quello che trovi è:

  • Funzione getrand : questo è solo un PRNG che restituisce un numero da 0 fino a upto .
  • Funzione randselect : questa è la funzione che randmoly sceglie n numeri univoci di molti numeri. Questo è ciò di cui tratta questa domanda.
  • Funzione main : questo è solo per dimostrare un uso per altre funzioni, in modo da poterlo compilare in un programma e divertirsi.
 #include  #include  int getrand(int upto) { long int r; do { r = rand(); } while (r > upto); return r; } void randselect(int *all, int end, int select) { int upto = RAND_MAX - (RAND_MAX % end); int binwidth = upto / end; int c; for (c = 0; c < select; c++) { /* randomly choose some bin */ int bin = getrand(upto)/binwidth; /* swap c with bin */ int tmp = all[c]; all[c] = all[bin]; all[bin] = tmp; } } int main() { int end = 1000; int select = 5; /* initialize all numbers up to end */ int *all = malloc(end * sizeof(int)); int c; for (c = 0; c < end; c++) { all[c] = c; } /* select select unique numbers randomly */ srand(0); randselect(all, end, select); for (c = 0; c < select; c++) printf("%d ", all[c]); putchar('\n'); return 0; } 

Ecco l'output di un codice di esempio in cui output casualmente 4 permutazioni su un pool di 8 numeri per 100.000.000 molte volte. Quindi uso quelle molte permutazioni per calcolare la probabilità di avere ogni permutazione unica. Quindi li ordino secondo questa probabilità. Si nota che i numeri sono abbastanza vicini, il che significa che è distribuito uniformsmente. La probabilità teorica dovrebbe essere 1/1680 = 0,000595238095238095 . Nota come il test empirico è vicino a quello teorico.