5

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.

Community
  • 1
amcalde
  • 4,674

2 Answers2

8

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.

hmakholm left over Monica
  • 286,031
  • Thanks! I will try this out and be sure to understand it, I'll select it as the answer after I get that chance. – amcalde May 30 '15 at 01:30
  • Works beautifully--thanks. I want to be like you when I grow up. – amcalde Jun 01 '15 at 15:19
  • If I may, I'll try to spell out why this works: Basically, in the first case there is nothing left to do. In the second you CAN put a $0$ in first ( since $n$ satisfies the inequality there) and since we want lexicographically ordered items, we DO put a $0$ in and then we must fill out the rest. Finally we must put a $1$ down, then deal with the consequences as spelled out. – amcalde Jun 01 '15 at 20:22
  • 1
    Beautiful. One important thing to note: that $n\le \binom{m-1}k$ is only suitable when $n$ is indexed from 1. If $n$ is indexed from 0, that test should be $n< \binom{m-1}k$. – Stuart P. Bentley Jan 25 '18 at 11:23
  • Just to be sure, you are assuming that ${m-1 \choose k} = 0$ when $k>m-1$ ? – Ywen Nov 28 '23 at 12:34
0

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.

P Vanchinathan
  • 19,504
  • That's what I thought at first. But the OP is looking for the next permutation of the digits, so you can't change the number of 1s. It's not obvious (to me) that there's a straightforward way to add 1 in a loop until you have the same number of 1's and 0's as when you started. – Ethan Bolker May 30 '15 at 00:25