Computing the $n^{\textrm{th}}$ permutation of bits.

Question

I've seen this post about the $n^{\textrm{th}}$ permutation of a set but that is not what I need. If you have a bit string (ones and zeros only) there are algorithms to quickly permute the NEXT lexicographically ordered bit permutation. For example take $$000111 \rightarrow 001011 \rightarrow 001101\rightarrow\cdots$$ etc. If the string is long then there are going to be approximately one Bajillion of these things. And I want to know how to compute the $n^{\textrm{th}}$ guy without doing the exhaust.

Backgound: This is for a parallel computing job where I need to farm out the search space of elements of a set.

Foreground: I own a copy of Knuth's 4th volume of "The Art of Computer Programming" and I think the answer is in there but I can't seem to find it. (It's like 900 pages).

I'm posting here in the hopes that someone has knowledge of this (obviously). Even if you can point me to a source, say the part in Knuth's book where he describes this problem I would be most grateful.

Answer 1

This recursive algorithm computes the $f(n,m,k)$, the $n$th string of $m$ symbols of which $k$ are ones:

$$f(n,m,k) = \begin{cases} \epsilon & \text{when }m=0 \\ \mathtt 0.f(n,m-1,k) & \text{when }m\ge1 \text{ and }n\le \binom{m-1}k \\ \mathtt 1.f(n-\binom{m-1}k,m-1,k-1) & \text{otherwise} \end{cases} $$

Precomputing the binomial coefficients may be useful if you need to do this many times.

Answer 2

Every bit string of length $n$ is the binary representation of numbers from $0$ to $2^n-1$. So take theset of integers less than $2^n$ in their natural order and write them out in binary.