Come selezionare uno dei n oggetti a caso senza conoscere n all'inizio?

Per la concretezza, come leggeresti la linea di testo e selezionerai e stamperai una riga a caso, quando non conosci il numero di linee in anticipo?Come selezionare uno dei n oggetti a caso senza conoscere n all'inizio?

Sì, questo è un problema di programmazione perla che mi confonde.

La soluzione sceglie il primo elemento, quindi seleziona il secondo con probabilità 1/2, il terzo con 1/3 e così via.

Un algoritmo:

i = 0 
while more input lines 
    with probability 1.0/++i 
    choice = this input line 
print choice

Supponiamo che la scelta finale è il 3 ° elemento, la probabilità è 1 x 1/2 x 1/3 x 3/4 x ... x n-2/n-1 x n-1/n == 1/2n? Ma 1/n dovrebbe essere corretto.

fonte

2011-09-01 deepsky

La probabilità che l'elemento 3 sia scelto non dipende affatto da ciò che è stato scelto nel passaggio 1 o 2. Pertanto, non si includono i termini 1 o 1/2 qui. Quindi è 1/n. –

Grazie. Ha senso ora. – deepsky

domanda interessante, non ci hai mai pensato! – unkulunkulu

L'algoritmo è corretto, ma l'analisi no. Puoi dimostrarlo per induzione. Loosely: funziona per N = 1, naturalmente. Se funziona fino a N-1, allora cosa succede a N? La possibilità che l'elemento Nth venga scelto e sovrascriva l'ultima scelta è 1/N - buono. La possibilità che non lo sia è (N-1)/N. In tal caso viene utilizzata la scelta del passaggio precedente. Ma a quel punto tutti gli elementi avevano una possibilità 1/(N-1) di essere scelti. Ora è 1/N. Buona.

fonte

2011-09-01 07:24:22

-1

Questo non è davvero casuale, poiché è più probabile che tu scelga una riga all'inizio del file. Devi conoscere il numero di linee per renderlo casuale. (50% delle volte che si ottiene la prima riga!)

fonte

2011-09-01 07:19:19

è casuale. il fatto che non sia [Distribuzione uniforme] (http://en.wikipedia.org/wiki/Uniform_distribution_%28discrete%29), non lo rende casuale. – amit

Si noti che l'algoritmo non * restituisce * se viene scelta una linea. Diventa solo la scelta attuale. Funziona. –

@sean - Sei corretto. Ma in tal caso la scelta non sarà unifom. Sarà più alto verso la fine del file. –

Metodo 1: effettuare una prima passata per determinare quante linee ci sono. Quindi randomizzalo.

Metodo 2: utilizza il metodo che hai menzionato. Funziona, ma non darà a ogni linea la stessa possibilità di essere selezionato.

Per quanto posso dire, non è possibile modificare il metodo 2 per dare a ogni linea la stessa possibilità di essere scelto. È matematicamente possibile che il numero di linee sia illimitato all'infinito.

fonte

2011-09-01 07:22:24 Mysticial

L'algoritmo è corretto. Se questo programma ha a che fare con un flusso infinito di input è una domanda diversa, ma l'OP suggerisce che ci sia una dimensione finita per l'input; è solo non noto. –

il calcolo è sbagliato:

Supponiamo che la scelta finale è il 3 ° elemento, la probabilità è 1 x 1/2 x 1/3 x 3/4 x ... x n-2/n-1 x n-1/n

La probabilità reale è:

(1 x 1/2 + 1 x 1/2) x 1/3 x 3/4 x .. x n-2/n-1 x n-1/n == 1/n

poiché o si scelsero 2 o voi non ha scelto 2 (scegliendo 2 ha una proba di 1/2 e non scegliendo 2 a proba di 1/2)

fonte

2011-09-01 07:36:30

Leggi 1 Leggi 2 il 50% di possibilità di una , tienilo, scartalo. Leggi 3 (dovremmo avere 1 e 3 o 2 e 3). 50% di possibilità su una delle linee, scartare l'altra. Continua a lavorare con una probabilità del 50% lungo tutto il file, questo ti lascia con 2 linee. Prendi un 50/50 su una delle linee e hai una linea a caso. Le probabilità erano pari all'intero file.

fonte

2011-09-08 01:40:24

Stai insinuando con la tua ultima frase che la probabilità di essere scelta è la stessa per ogni riga del file con questo algoritmo? Perché non sarebbe il caso. La distribuzione di probabilità effettiva sarebbe esponenziale. – zinglon

Come selezionare uno dei n oggetti a caso senza conoscere n all'inizio?

risposta

Problemi correlati