![binary generator algorithm binary generator algorithm](https://ars.els-cdn.com/content/image/3-s2.0-B978012811129100002X-fx001.gif)
I modified it to use 0-based indexing, as well as adding the code to keep track of the binary representations. The one in the sample code below comes from Frank Ruskey's unpublished manuscript on Combinatorial Generation (Algorithm 5.7 on page 130). This sequence can be produced by a recursive algorithm similar to that suggested by - the only difference is that the second half of each recursion needs to be produced in reverse order - but it's convenient to use a non-recursive version of the algorithm.
![binary generator algorithm binary generator algorithm](https://cdn.ilovefreesoftware.com/wp-content/uploads/2018/02/4-Best-Free-Binary-Search-Tree-Generator-Websites.png)
I wanted to underline them but for some inexplicable reason SO allows strikethrough but not underline.) 1 11 000 0 1 0110 1 00011 0 1 0101 Here's an example for n=6, k=3: (The bold bits are swapped at each step. It is always possible to find a Gray code. This could be ameliorated slightly by starting the iteration at a random position in the sequence.) (For example, for the case where n is 4 and k is 2, there are 6 possible words which could be sequenced in 6! (720) different ways, but there are only 4! (24) bit-shuffles. Also, for small values of n the number of possible bit shuffles is very limited, so there will not be a lot of different sequences produced. (This is also known as a "revolving-door" iteration because as each new 1 is added, some other 1 must be removed.) This allows the bit mask to be updated rapidly, but it means that successive entries are highly correlated, which may be unsuitable for some purposes. In order to avoid the complication of shuffling actual bits, the words can be generated in a Gray code order in which only two bit positions are changed from one word to the next. The fastest one (I think) is to first generate a random shuffle of bit values, and then iterate over the possible words one at a time applying the shuffle to the bits of each value. (C implementations of the two solutions follow the text.) 1. That's easy and unbiased (as long as you use a good random number generator to do the shuffle) but it can use a lot of memory if n is large, particularly if you are not sure you will need to complete the iteration.īut there are a couple of solutions which do not require keeping all the possible words in memory. If you have enough memory to store all the possible bit sequences, and you don't mind generating them all before you have the first result, then the solution would be to use some efficient generator to produce all possible sequences into a vector and then shuffle the vector using the Fisher-Yates shuffle.