Geek Answers Handbook

Given an array of booleans, what is the most efficient way to select a random value index TRUE?

You are given an array of size n containing arbitrary boolean values.

What is the fastest way to return a random value index TRUE.

The algorithm should randomly return any of the indices containing TRUE.

+5
source share
5 answers

Something like that:

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;
        }
    }
}

So, for 4 values, for example, you get the following probabilities for your indices:

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

The EDIT: . Steve Jessop noted that floating-point comparisons will ultimately lead to very uneven choices. Assuming what unit_randomis defined as rand() / RAND_MAX, the comparison can be changed to:

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

- rand, .

+5

- - , , , . , , O (1); , , O (n) ( 1/n , n). , .

, , , .

+1

, " ". " "? , , , " " (, " " ) ( "" .) 1/2. , . , , , .

0

To return it, you must first count the True values ​​(there is no way to skip this) and copy their indices into another array. And after counting, you just need to generate a random integer from 0 to N-1 (where N is the number of True values) and select a value from the created array.

in pseudo python:

indices=[]

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

A simple solution: generate a permutation of the possible indices (1: n?) And in the order of that index of the permutation return, if the corresponding value is true

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

More articles:


All Articles