Come generare un elenco di numeri interi casuali ascendenti

Question

Ho una raccolta esterna contenente n elementi che voglio selezionare un certo numero (k) di essi casualmente, emettendo gli indici di tali elementi in qualche file di dati serializzato. Voglio che gli indici siano prodotti in ordine crescente e che non ci siano duplicati. Sia n che k possono essere abbastanza grandi e generalmente non è possibile memorizzare semplicemente interi array in memoria di quella dimensione.

Il primo algoritmo che ho trovato era quello di scegliere un numero casuale r [0] da 1 a nk ... e quindi scegliere un numero casuale successivo r [i] da r [i-1] +1 a n -k + i, ha solo bisogno di memorizzare due voci per "r" in qualsiasi momento. Tuttavia, un'analisi abbastanza semplice rivela che la probabilità di selezionare numeri piccoli è incoerente con quello che avrebbe potuto essere se l'intero set fosse equamente distribuito. Ad esempio, se n era un miliardo e k era mezzo miliardo, la probabilità di selezionare la prima voce con l'approccio che ho appena descritto è molto piccola (1 su mezzo miliardo), dove in realtà dal momento che metà delle voci sono essendo selezionato, il primo dovrebbe essere selezionato il 50% delle volte. Anche se utilizzo l'ordinamento esterno per ordinare k numeri casuali, dovrei scartare qualsiasi duplicato e riprovare. Man mano che k si avvicina a n, il numero di tentativi continuerebbe a crescere, senza alcuna garanzia di risoluzione.

Mi piacerebbe trovare un algoritmo O (k) o O (k log k) per fare ciò, se è possibile. Il linguaggio di implementazione che userò è C++ 11, ma le descrizioni in pseudocodice potrebbero comunque essere utili.

Answer 1

È possibile risolvere questo in modo ricorsivo a O (log k k) se si partizionare nel bel mezzo della vostra gamma, e in modo casuale campionare dal hypergeometric probability distribution di scegliere quanti valori si trovano sopra e sotto il punto di mezzo (cioè il valori di k per ogni sottosequenza), quindi ricorsivamente per ogni:

int sample_hypergeometric(int n, int K, int N) // samples hypergeometric distribution and 
// returns number of "successes" where there are n draws without replacement from 
// a population of N with K possible successes. 
// Something similar to scipy.stats.hypergeom.rvs in Python. 
// In this case, "success" means the selected value lying below the midpoint. 
{ 
    std::default_random_engine generator; 
    std::uniform_real_distribution<double> distribution(0.0,1.0); 

    int successes = 0; 
    for(int trial = 0; trial < n; trial++) 
    { 
     if((int)(distribution(generator) * N) < K) 
     { 
      successes++; 
      K--; 
     } 
     N--; 
    } 
    return successes; 
} 

select_k_from_n(int start, int k, int n) 
{ 
    if(k == 0) 
     return; 
    if(k == 1) 
    { 
     output start + random(1 to n); 
     return; 
    } 

    // find the number of results below the mid-point: 
    int k1 = sample_hypergeometric(k, n >> 1, n); 
    select_k_from_n(start, k1, n >> 1); 
    select_k_from_n(start + (n >> 1), k - k1, n - (n >> 1)); 
} 

campionamento dal binomial distribution potrebbe anche essere usato per approssimare la distribuzione ipergeometrica con p = (n >> 1)/n, dove campioni di rigetto k1> (n >> 1).

Answer 2

Come menzionato nel mio commento, utilizzare uno std::set<int> per memorizzare gli interi generati casualmente in modo tale che il contenitore risultante sia ordinato e non contenga duplicati. Esempio di codice frammento:

#include <random> 
#include <set> 

int main(void) { 
    std::set<int> random_set; 
    std::random_device rd; 
    std::mt19937 mt_eng(rd()); 
    // min and max of random set range 
    const int m = 0; // min 
    const int n = 100; // max 
    std::uniform_int_distribution<> dist(m,n); 

    // number to generate 
    const int k = 50; 
    for (int i = 0; i < k; ++i) { 
     // only non-previously occurring values will be inserted 
     if (!random_set.insert(dist(mt_eng)).second) 
      --i; 
    } 
} 

Answer 3

Potrebbe regolare ogni selezione indice ascendente in un modo che compensa la distorsione probabilità si sta descrivendo?

IANAS, ma la mia ipotesi sarebbe che se si seleziona un numero casuale r tra 0 e 1 (che si ridimensiona all'intero intervallo di indice rimanente dopo la regolazione), si potrebbe essere in grado di regolarlo calcolando r^(x) (mantenendo l'intervallo in 0..1, ma aumentando la probabilità di numeri più piccoli), con x selezionato risolvendo l'equazione per la probabilità della prima immissione?

Answer 4

Supponendo che non è possibile memorizzare numeri casuali k nella memoria, sarà necessario generare i numeri in ordine casuale rigoroso. Un modo per farlo sarebbe quello di generare un numero compreso tra 0 e n/k. Chiama quel numero x. Il prossimo numero che devi generare è compreso tra x+1 e (n-x)/(k-1). Continua in questo modo finché non hai selezionato k numeri.

Fondamentalmente, si sta dividendo l'intervallo rimanente per il numero di valori rimasti da generare e quindi generando un numero nella prima sezione di tale intervallo.

Un esempio. Si desidera generare 3 numeri compresi tra 0 e 99 inclusi. Quindi per prima cosa generi un numero compreso tra 0 e 33. Supponi di scegliere 10.

Quindi ora hai bisogno di un numero compreso tra 11 e 99. L'intervallo rimanente è composto da 89 valori e hai ancora due valori da selezionare. Quindi, 89/2 = 44. Hai bisogno di un numero compreso tra 11 e 54. Supponi di aver scelto 36.

Il tuo intervallo rimanente va da 37 a 99 e hai un numero a sinistra tra cui scegliere. Quindi scegli un numero a caso tra 37 e 99.

Questo non ti darà una distribuzione normale, poiché una volta scelto un numero è impossibile ottenere un numero inferiore a quello in una scelta successiva. Ma potrebbe essere abbastanza buono per i tuoi scopi.

Questo pseudocodice mostra l'idea di base.

pick_k_from_n(n, k) 
{ 
    num_left = k 
    last_k = 0; 
    while num_left > 0 
    { 
     // divide the remaining range into num_left partitions 
     range_size = (n - last_k)/num_left 
     // pick a number in the first partition 
     r = random(range_size) + last_k + 1 
     output(r) 
     last_k = r 
     num_left = num_left - 1 
    } 
} 

Si noti che questo richiede O (k) tempo e richiede O (1) spazio aggiuntivo.

Answer 5

È possibile farlo in tempo O (k) con l'algoritmo di Floyd (non Floyd-Warshall, è una cosa da percorso più breve). L'unica struttura dati di cui hai bisogno è una tabella a 1 bit che ti dirà se un numero è già stato selezionato o meno. Cercare una tabella hash può essere O (1), quindi questo non sarà un peso, e può essere tenuto in memoria anche per n molto grandi (se n è veramente enorme, dovrai usare un filtro b-tree o bloom o qualcosa).

per selezionare le voci k tra n:

for j = n-k+1 to n: 
    select random x from 1 to j 
    if x is already in hash: 
    insert j into hash 
    else 
    insert x into hash 

Questo è tutto. Alla fine, la tua tabella hash conterrà un campione uniformemente selezionato di k elementi tra n. Leggili in ordine (potresti dover scegliere un tipo di tabella hash che lo consenta).

Answer 6

Se in pratica k ha lo stesso ordine di grandezza n, forse molto semplice O (n) algoritmo sarà sufficiente:

assert(k <= n); 
std::uniform_real_distribution rnd; 
for (int i = 0; i < n; i++) { 
    if (rnd(engine) * (n - i) < k) { 
     std::cout << i << std::endl; 
     k--; 
    } 
} 

Produce tutte le sequenze ascendenti con uguale probabilità.