Random bits with a specified density (Bernoulli Trials) I'm sure this is a fully 'solved' problem and expecting cross references but I can't find this on Google. I'm probably missing a keyword.

Here is a naive function for populating a bool array (b[i]) of length N in a Bernoulli distribution.
P(b[i]==true)==p and P(b[i]==false)==(1-p) for each independent random variable b[i].

#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;
#include &lt;stdbool.h&gt;

void randomize(bool*const bits,const size_t len,double p){

    for(size_t i=0;i&lt;len;++i){
        if(p&gt;=1.0||rand()&lt;p*RAND_MAX){//Need to force the hand for p&gt;=1.0 as 0 and RAND_MAX possible.
            bits[i]=true;
        }else{
            bits[i]=false;
        }
    }
}

int main(void) {

    const size_t len=100;//N in the text.
    bool* bits=malloc(len*sizeof(*bits));//b[i] in the text.
    if(bits==NULL){
        return EXIT_FAILURE;
    }

    srand(1234);//Fixed for Reproducibility.

    randomize(bits,len,0.3);

    int count=0;
    for(size_t i=0;i&lt;len;++i){
        printf("%c" , (bits[i]?'1':'0'));
        if(bits[i]){
            ++count;
        }
    }
    printf("\ncount=%f\n",((double)count)/((double)len));

    free(bits);

    return EXIT_SUCCESS;
}


Obviously it's linear \$\mathcal{O}(N)\$ for 'seeks' in the array.

However I could start with an array full of (0) and calculate a random variable (\$B\$) in the binomial distribution to get the number of bits to set then select them at random.

If \$p\$ is small that will involve far fewer seeks. It will still be (expected) asymptotically linear but with a far reduced constant.

If I naively pick the \$B\$ elements to set I might pick the same one twice (Birthday Paradox anyone?) and will need to pick again. If I just 'scan' forwards to the first free slot I will introduce a 'clumping' bias and violate the independence of the random variables P(b[i+1]==1|b[i]==1)&gt;p. Clumping is a no-no for my application.

Therein lies the rub. If \$p\$ is near to 1.0 it will take an increasingly massive amount of time to fill the array. When it's nearly full randomly picking a 0 will typically take a lot of retries.

I can be 'clever' and if \$B \gt \frac{N}{2}\$ I can block set to 1 and set \$N-B\$ back to 0. That means only counting 'seeks' I will always beat the full scan above.
That's because the average retries at each step is \$\le 1 \$so expected seek count is \$ \lt N\$.

Does anyone have such a piece of code readily on hand?

PS: The data structure I'm working with isn't an array; it's a particular kind of tree. That's not important but might explain why I'm counting 'seeks' as the overriding parameter. However I am able to easily conjure up a 'tree of false' and a 'tree of true' to implement that 'block fill' requirement.
For what I can see, the code fills an array with a given amounts of true values (the rest being false) in random order. I'd rather initialize first p*N elements to true, and then random_shuffle the array.

That said I don't understand why you need this array at all. Can we see how your application uses it?