How do you enumerate all the possible subsets of x y z in C plus plus?

Answer 1

Enumerating subsets requires that each element in the set be mapped to a bit value. Combining these bit values (with logical OR) gives you the subset. Each subset will then have a value in the range 0 to 7, giving 8 subsets in all: {}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}. However, you cannot simply count from 0 to 7 to enumerate these subsets because this is highly inefficient. In a set of 3 it's not a significant loss, but in a larger set the inefficiency is substantial. For instance, in a set of just 64 elements, you must count from 0 to 9,223,372,036,854,775,809 in order to enumerate the 64 subsets that have just one element. If that doesn't drive the point home, then nothing will.

In order to correctly enumerate subsets you must use the Banker's sequence. Each sequence varies depending upon how many elements are in the set, however the sequence allows you to quickly enumerate one set after another in a logical sequence. It also allows you to start from anywhere in the sequence and continue from that point on, thus making it possible to quickly enumerate all sets with a specific number of elements.

The following code is quite involved but includes several auxiliary functions that help speed up the main code at the bottom. Some examples are included to demonstrate different usages, including the enumeration of subsets of {x, y, z}, subsets of a set of 5 elements and subsets of a subset of a 9 element set. Note that the final example (all subsets of a 32 element set) is commented out because it will take a seriously long time to enumerate all the possible subsets. However, the code is flexible enough to allow you to narrow the search down to just those subsets with a specific number of elements.

Note that the two main functions to focus upon are the find_first_subset() and find_next_subset() functions. These two functions are the driving force behind the Banker's sequence.

#include

// Returns the count of set bits in the given subset.

// E.g., 01010010 returns 3.

unsigned int count_set_bits( register unsigned int subset )

{

// An alternative method is to logical AND the bitset with 0x1

// then right shift the bitset by 1 bit. That requires an average

// of 32 separate operations (worst case is 64). This method always

// uses 17, thus always returns in constant time. For unsigned

// short, eliminate the last shift. For char, eliminate the last

// two shifts.

subset -= (( subset >> 1 ) & 0x55555555 );

subset = ((( subset >> 2 ) & 0x33333333 ) + ( subset & 0x33333333 ));

subset = ((( subset >> 4 ) + subset ) & 0x0f0f0f0f );

subset += ( subset >> 8 );

subset += ( subset >> 16 );

return( subset & 0x0000003f );

}

// Returns all set bits from the given subset's MSB down.

// E.g., 00100010 returns 00111111.

// The inversion of the return value can be used to mask

// bits that are greater than the MSB in another subset.

unsigned int fill_down( register unsigned int subset )

{

subset |= ( subset >> 1 );

subset |= ( subset >> 2 );

subset |= ( subset >> 4 );

subset |= ( subset >> 8 );

subset |= ( subset >> 16 );

return( subset );

}

// Returns the least-significant set bit in the given subset.

// E.g., 00100110 returns 00000010.

unsigned int get_LSB( register unsigned int subset )

{

return( subset ^ ( subset & ( subset - 1 )));

}

// Returns the most-significant set bit in the given subset.

// E.g., 00100110 returns 00100000.

unsigned int get_MSB( register unsigned int subset )

{

subset = fill_down( subset );

return( subset & ~( subset >> 1 ));

}

// Returns the first subset of subset_count within the given set.

// The return value can be passed to get_next_subset().

unsigned int get_first_subset( const unsigned set, unsigned int subset_count )

{

// Initialise the subset.

unsigned int subset = 0;

// Check validity of parameters.

if( subset_count && subset_count <= count_set_bits( set ))

{

// Assign the least-significant bit of set to subset.

subset = get_LSB( set );

// Repeatedly eliminate the LSB from set and

// combine the next LSB to subset until we've

// filled the subset up to the required count.

while( --subset_count )

subset |= get_LSB( set & ~fill_down( subset ));

}

// The first subset is complete (or is 0).

return( subset );

}

// Returns the next subset of the given bitset that follows previous_subset.

// The return value can be passed back to this function to get the next subset.

unsigned int get_next_subset( const unsigned set, const unsigned previous_subset )

{

// Initialise the next subset.

unsigned int next_subset = 0;

// Check validity of parameters.

if( previous_subset )

{

// Locate the MSB from the previous_subset.

unsigned int bit = get_MSB( previous_subset );

// Eliminate the MSB from the next subset.

next_subset = previous_subset & ~bit;

// Locate the next available bit in the set, if any.

if( bit = get_LSB( set & ~fill_down( bit )))

// The next subset is complete.

next_subset |= bit;

// Make recursive call using the set without its MSB

// Note: the subset we pass has already already been reduced.

else if( next_subset = get_next_subset( set & ~get_MSB( set ), next_subset ))

// Locate the next available bit in the original set

// At least one bit is guaranteed to exist: the MSB

// we eliminated from the recursive call.

next_subset |= get_LSB( set & ~fill_down( next_subset ));

}

return( next_subset );

}

// Prints the subset (only prints the least-significant count of bits).

void print_subset( unsigned int subset, unsigned int bits )

{

const unsigned int max_bits = 32;

if( bits > max_bits )

return;

unsigned int i = 0;

// Skip any redundant bits...

for( ; i

// Begin printing.

for( ; i

std::cout << (( subset & 0x80000000 ) ? "1" : "0" );

std::cout << std::endl;

}

// Enumerate all subsets of set (only the least-significant count of bits),

void enumerate_subsets( unsigned int set, unsigned int bits )

{

std::cout << "From the set of:" << std::endl;

print_subset( set, bits );

for( unsigned int subset_count = 0; subset_count <= count_set_bits( set ); ++subset_count )

{

std::cout << "Subsets of " << subset_count << ":" << std::endl;

unsigned int subset = get_first_subset( set, subset_count );

do print_subset( subset, bits );

while( subset = get_next_subset( set, subset ));

}

}

// Enumerate all subsets of the set {x, y, z}

void enumerate_subsets_xyz( void )

{

unsigned int set = 1 | 2 | 4; // {x=1, y=2, z=4}

unsigned int bits = 3;

std::cout << "From the set of:\n{xyz}" << std::endl;

for( unsigned int subset_count = 0; subset_count <= count_set_bits( set ); ++subset_count )

{

std::cout << "Subsets of " << subset_count << ":" << std::endl;

unsigned int subset = get_first_subset( set, subset_count );

do{

std::cout << "{";

if( subset & 1 ) std::cout << "x";

if( subset & 2 ) std::cout << "y";

if( subset & 4 ) std::cout << "z";

std::cout << "}" << std::endl;

}while( subset = get_next_subset( set, subset ));

}

}

// Test functions.

int main()

{

// Enumerate all subsets of the set {x, y, z} (3 bits)

enumerate_subsets_xyz();

std::cout << std::endl;

// Enumerate all subsets of the set 11111 (5 bits)

enumerate_subsets( 0x1f, 5 );

std::cout << std::endl;

// Enumerate subsets of the subset 101010101 (9 bits total but only 5 selected)

enumerate_subsets( 0x155, 9 );

std::cout << std::endl;

//// Just for the hell of it, let's enumerate all possible sets for all 32 bits.

//enumerate_subsets( 0xffffffff, 32 );

//std::cout << std::endl;

return( 0 );

}