Dato un array di booleani, qual è il modo più efficace per selezionare l'indice di un valore TRUE casuale?

Question

Viene fornita una matrice di dimensione n, contenente valori booleani arbitrari.

Qual è il modo più veloce per restituire l'indice di un valore VERO casuale.

L'algoritmo deve restituire a caso uno qualsiasi degli indici contenenti un VERO.

Answer 1

Qualcosa di simile a questo:

int count = 0; 
int index = -1; 
for (int i = 0; i != n; ++i) 
{ 
    if (values[i]) 
    { 
     ++count; 
     if (unit_random <= 1.0f/count) 
     { 
      index = i; 
     } 
    } 
} 

Così per 4 valori per esempio, si ottengono i seguenti probabilità per i loro indici:

1: (1/1) * (1/2) * (2/3) * (3/4) = 1/4 
2: (1/2) * (2/3) * (3/4) = 1/4 
3: (1/3) * (3/4) = 1/4 
4: 1/4 = 1/4 

EDIT: Come Steve Jessop ha sottolineato il punto di confronto floating alla fine porterà a una selezione molto non uniforme. Supponendo unit_random è definito come rand()/RAND_MAX il confronto può essere cambiato in:

typedef unsigned long long u64; 
u64 product = u64(count) * rand(); 
if (product <= u64(RAND_MAX)) 

Questo non darà perfetta distribuzione a causa della natura discreta rand ma sarà meglio.

Answer 2

Non è del tutto chiaro cosa significhi "randomly distibuted". Significa "con qualche distribuzione sconosciuta"? Se è così, facciamo finta che tutte le possibili distribuzioni siano ugualmente probabili, quindi la "distribuzione attesa" (come in "valore atteso") è uniforme (la "media" di tutte le possibili distribuzioni). Quindi qualsiasi indice è VERO con una probabilità di 1/2. Quindi il tuo compito diventa il compito di iterare attraverso l'array il più rapidamente possibile. Inizia dall'inizio, come se fosse normale iterare un array, finché non si incontra un valore TRUE.

Answer 3

Per restituirlo, è necessario prima contare i valori True (non c'è modo di saltarlo) e accumulare i loro indici in un altro array. E dopo aver contato devi solo generare un numero intero casuale da 0 a N-1 (dove N è il numero di valori True) e scegliere il valore dall'array creato.

in pseudo-python:

indices=[] 

for i,val in enumerate(arr): 
    if val: 
     indices.append(i) 
randi = randint(0,len(indices)-1) 
return indices[randi] 

Answer 4

La soluzione più veloce - a patto che non si seleziona più volte sullo stesso array - è quello di scegliere un indice a caso, restituirlo se è vero, e ripetere se non. Nel migliore dei casi, dove tutte le voci sono vere, questo è O (1); nel peggiore dei casi, dove una sola voce è vera, questa è O (n) (ogni tentativo ha una probabilità di 1/n di colpire l'unico valore vero, il che significa un numero atteso di tentativi di n). Questo non è peggio di nessuna delle altre soluzioni pubblicate.

Se si prevede che la matrice di solito sia quasi completamente falsa, tuttavia, è possibile scegliere un'altra soluzione, poiché la varianza in fase di esecuzione di questo metodo casuale sarà elevata.

Answer 5

Soluzione semplice: Genera una permutazione di possibili indici (1: n) e nell'ordine di tale indice di ritorno permutazione se il valore corrispondente è vero

def randomTrue(x): 
    perm = randomPermute(0:len(x)) 
    for i in perm: 
     if x[i]: 
      return i