For a given positive integer $N$, is there an efficient algorithm to generate all $N$-bit numbers in such an order that the number of 1s in the binary representation increases monotonically?
Asked
Active
Viewed 224 times
1 Answers
2
To generate all $n$-bit numbers with $k$ ones, start out with the $k$ ones at the left, and in each step, move the right-most one that's followed by a zero to the right and move all ones following it right behind it; e.g.:
$$ 11100,11010,11001,10110,10101,10011,01110,01101,01011,00111\;. $$
You can keep a pointer to the $1$ that you're currently moving to the right, which also tells you how many ones to move to the left when this one can no longer move. For $k\gt n/2$, it will be more efficient to move the zeros instead of the ones.
joriki
- 238,052
-
-
If you reverse this, it seems to be a monotonic increasing code (alas only for the weight level). It is like $k$ soldiers (1's) passing a river (0's) one after another.. – mvw Mar 30 '16 at 09:25
-
See also pre-fascicle 3a of Knuth's The Art of Computer Programming: "Generating All Combinations". – joriki Mar 30 '16 at 09:27
-
I expected this to be in Vol 4., because it is similar to monotonic Gray codes. My print copy is in the cellar. Need the ebook. :) – mvw Mar 30 '16 at 09:29
-
2