The key idea to my solution is the observation that the problem

*"Give me all numbers with \(k\) ones in its binary representation"*is very similar to calculating the binomial coefficient. Consider the following table containing all 5 digit numbers with 3 ones.

\(i\) | \(N_{10}\) | \(N_2\) |

0 | 28 | 11100 |

1 | 26 | 11010 |

2 | 25 | 11001 |

3 | 22 | 10110 |

4 | 21 | 10101 |

5 | 19 | 10011 |

6 | 14 | 01110 |

7 | 13 | 01101 |

8 | 11 | 01011 |

9 | 7 | 00111 |

Naturally, the number of items equals the binomial coefficient 5 over 3.

In order to calculate the correct number at an index \(i \in [0,9]\), we need to know how many ones are at the top and how many zeros are at the bottom for the first column. This happens to be the quotient of \(3 \over 5\) times the binomial coefficient 5 over 3. This is true for any combination of \(n\) and \(k\). Finally, after knowing whether we're in the upper or lower half of the table, we can dismiss the first column and analyze the remaining \(n-1\) columns.

The Code

As usual, here the necessary code snippets for your own project. You're going to need an implementation of the binomial coefficient. Instead of using the standard version, you might want to use this optimized version without explicitly calling the factorial function.

int binomial(int _n, int _k) { if(_k < _n-_k) _k = _n-_k; int c = 1; for(int i=0; i<_k; ++i){ c = c*(_n-i); c = c/(i+1); } return c; }

And finally the actual binary filter function in a recursive implementation. The function will return the \(i\)-th, \(n\) digit number with \(k\) ones in its binary representation. The order of values is descending.

int bfilter(int _n, int _k, int _i) { if(_n < =0) return 0; //Number of "1"s int n_x = (_k*binomial(_n, _k))/_n; //_i is in "1" block if(_i < n_x){ return pow(2, (_n-1)) + bfilter(_n-1, _k-1, _i); } //_i is in "0" block else{ return bfilter(_n-1, _k, _i-n_x); } }

Check out the ▷docs for further information.

## No comments:

## Post a Comment