I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 < n < 64$ and return a pseudo-random 64-bit number with exactly $n$ bits set to $1$, and the rest set to 0.My current approach involves something like this:Generate a pseudorandom 64-bit number $k$.Count the bits in $k$, storing the result in $b$.If $b = n$, output $k$; otherwise go to 1.This works, but it seems inelegant. Is there some kind of PRNG algorithm which can generate numbers with $n$ set bits more elegantly than this?
PRNG for generating numbers with n set bits exactly
algorithms;information theory;coding theory;pseudo random generators
What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern.This is known as enumerative coding, and it's one of the oldest deployed compression algorithms. Probably the simplest algorithm is from Thomas Cover. It's based on the simple observation that if you have a word that is $n$ bits long, where the set bits are $x_k \ldots x_1$ in most-significant bit order, then the position of this word in the lexicographic ordering of all words with this property is:$$\sum_{1 \le i \le k} { x_i \choose i}$$So, for example, for a 7-bit word:$$i(0000111) = { 2 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 0$$$$i(0001011) = { 3 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 1$$$$i(0001101) = { 3 \choose 3 } + {2 \choose 2 } + {0 \choose 1} = 2$$...and so on.To get the bit pattern from the ordinal, you just decode each bit in turn. Something like this, in a C-like language:uint64_t decode(uint64_t ones, uint64_t ordinal){    uint64_t bits = 0;    for (uint64_t bit = 63; ones > 0; --bit)    {        uint64_t nCk = choose(bit, ones);        if (ordinal >= nCk)        {            ordinal -= nCk;            bits |= 1 << bit;            --ones;        }    }    return bits;}Note that since you only need binomial coefficients up to 64, you can precompute them.Cover, T., Enumerative Source Encoding. IEEE Transactions on Information Theory, Vol IT-19, No 1, Jan 1973.