How to generate all binary patterns of length n with k bits set ? (using recursion)

Question

I would like to write a function that generates all binary patterns of length n with k bits set. The patterns could be stored in a 2-D array. It looks like I need recursion to achieve this. Any code or pseudocode would be helpful.

Example: if n=5 and k=3 generate this:

11100
11010
11001
10110
10101
10011
01110
01101
00011
00111

I found similar posts: Generate all binary strings of length n with k bits set, but the proposed solutions compute all 2^k combinations.

Surely this is the same question as https://stackoverflow.com/questions/46023719/what-is-an-efficient-code-for-generating-n-binary-digit-numbers-with-k-bits-set, asked just a few hours ago? (Except for the request for recursion, which is definitely not necessary for an efficient implementation.) — rici, Sep 04 '17 at 03:16
Also, the accepted answer to the question you link does *not* generate all 2^k combinations. Did you try it? — rici, Sep 04 '17 at 03:18
@rici the accepted answer to the question I linked to, takes a number as input: unsigned int v; // current permutation of bits unsigned int w; // next permutation of bits — david, Sep 04 '17 at 03:42
@David, that argument *v* is just the previous permutation. It is easy to call it with a first number, and then just keep calling it with the previous result returned by the function. Also there are several other useful answers to that question. This is a dupe. — trincot, Sep 04 '17 at 03:49
Possible duplicate of [Generate all binary strings of length n with k bits set](https://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set) — trincot, Sep 04 '17 at 03:49
The accepted answer in the other post is a method that generates all **integers** with exactly N '1' bits. That's different. — david, Sep 04 '17 at 03:59
@david: It generates numbers in *lexicographical order* so you just stop when the leading 1 bit exceeds the length you want. — rici, Sep 04 '17 at 04:02
@rici: I do not know the numbers (wouldn't numbers be too large ?), I want the function to take as inputs: the number of bits. e.g n=200 bits and k = 3 bits . — david, Sep 04 '17 at 04:22
If `n` is so large that you cannot represent the boolean sequence as a machine integer, then indeed the bit hack gets more complicated (although you can use bignum arithmetic). In [this answer](https://stackoverflow.com/a/14717440/1566221), I provide a regular expression solution (see the paragraph about line 5 of the sample program); the summary of the algorithm is "find the last `01` in the string, flip it to `10` and shift all the following `1`s all the way to the right." For large `n`, `k` better be pretty small. — rici, Sep 04 '17 at 04:38

score 0 · Answer 1 · answered Sep 04 '17 at 04:53

For i = 0...(1<<n)-1
    If countsetbits(i) == k
        Store into collection

Where countsetbits(i) is:

j = i
For b = 0...n
    If j == 0
        Return b
    j = j And (j - 1)

with your example, in which

n = 5, k = 3

You get

i     b j=0? j     And(j-1)          Return b   Main loop
0...6                                           less than k
7     0 No   111b  And 110b = 110b  
      1 No   110b  And 101b = 100b  
      2 No   100b  And 011b = 000b  
      3 Yes                          3          k, hence store into collection
8     0 No   1000b And 0111b = 0000b
      1 Yes                          1          less than k
9     0 No   1001b And 1000b = 1000b
      1 No   1000b And 0111b = 0000b
      2 Yes                          2          less than k
10    0 No   1010b And 1001b = 1000b
      1 No   1000b And 0111b = 0000b
      2 Yes                          2          less than k
11    0 No   1011b And 1010b = 1010b
      1 No   1010b And 1001b = 1000b
      2 No   1000b And 0111b = 0000b
      3 Yes                          3          k, hence store into collection
...
31    ...                            5          greater than k

Thank you. But isn't this running 2^n iterations? Which is what I am trying to avoid. — david, Sep 04 '17 at 05:09

score 0 · Answer 2 · answered Sep 04 '17 at 06:06

Recursive implementation of this task is very simple (Delphi and pseudocode)

  procedure GenKBits(Value, Position, N, K: Integer);
  begin
    if K = 0 then
      Output Value in binary
    else
      if (Position < N) then begin
        GenKBits(Value or (1 shl Position), Position + 1, N, K - 1); //set bit
        GenKBits(Value, Position + 1, N, K);             //use zero bit
      end;
  end;

call  GenKBits(0, 0, 4, 2) gives

0011
0101
1001
0110
1010
1100

How to generate all binary patterns of length n with k bits set ? (using recursion)

2 Answers2