Enumeration bitset with increasing weight. (C++ & Boost::dynamic_bitset) [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

How to implement the algorithm in C++? The task such, there is a bitset size N. Need to consistently go through all the bitset overhang k = 1,2, ... l, until the total number of sequences is not equal to M. That is, The result should be an array:

0 ... 001
0 ... 010
0 ... 100
...
1 ... 000
0 ... 011
0 ... 101
0 ... 110
....
....
etc

With a weight of 1 clear bitwise shift to the left. But how to handle the bitset with weight k = 2,3, ... while maintaining the mass of the algorithm I do not know. please help, can someone faced a similar challenge. Bitset implemented using boost :: dynamic_bitset. The C++ language.

Peter de Rivaz Peter de Rivaz · Accepted Answer · 2013-10-05T12:42:43

You may find this C code helpful.

The function make_sets generates all bitpatterns of a certain weight, so main calls it multiple times to first generate patterns with 1 set bit, then 2 set bits, etc.

#include <stdio.h>

#define BYTETOBINARYPATTERN "%d%d%d%d%d"
#define BYTETOBINARY(byte)  \
  (byte & 0x10 ? 1 : 0), \
  (byte & 0x08 ? 1 : 0), \
  (byte & 0x04 ? 1 : 0), \
  (byte & 0x02 ? 1 : 0), \
  (byte & 0x01 ? 1 : 0) 

/* Make all bitsets with bits_to_add set bits in the least significant num_bits bits 
The most significant bit are taken from high_bits.*/
void make_sets(int high_bits, int bits_to_add, int num_bits) {
    // Recurse on the position of the next set bit
    int i;
    if (bits_to_add) {
        for(i=bits_to_add-1;i<num_bits;i++)
            make_sets(high_bits + (1<<i), bits_to_add-1, i);
    } else {
        printf (BYTETOBINARYPATTERN"\n", BYTETOBINARY(high_bits));
    }
}

int main(int argc,char *argv[]) {
    int M;
    for(M=1;M<=5;M++)
        make_sets(0,M,5);
}

This produces the output:

Enumeration bitset with increasing weight. (C++ & Boost::dynamic_bitset) [closed]

1 Answers