CODEWITHSUNDEEP
algorithmdata-structuressubsetgray-code
Mark Lin
Mark Lin

Reputation: 55

What is the most efficient way to generate subsets?

What I want to do is as follows:

Input: n, for example n = 3

Output: {000, 001, 010, 011, 100, 101, 110, 111}, generate all the subsets and I don't care the order of the subsets

I have implemented a algorithm:

for (long i = 0, max = 1 << n; i < max; i++) {
    for (int j = 0; j < n; j++) {
        // check if the j bit is set to 1
        int isSet = (int) i &  1 << j;
        if (isSet > 0) {
            // if yes, set the corresponding jth bit of x as 1.
        }
    }
    // add x to results;
}

I know Gray Code can do something like this. But I am wondering which one is the most efficient way to generate subsets?

Upvotes: 1

Views: 830

Answers (1)

MrSmith42
MrSmith42

Reputation: 10151

I'm not sure what you exactly mean be 'most efficient', but if you look for speed optimization, you can only hope for some minor optimizations because I doubt you can find a faster algorithm.

If you want to improve speed, you an try (always profile if this really speeds up your code!):

  • outer loop: make a version which uses int instead of long if max is small enough to fit in an int. This might be faster.
  • inner loop: you can calculate all bit-test masks outside both loops and store them in an array. This way you replace 1 << j by an array lookup. [I am not sure if this will improve speed, but it's worth a try]

You also should replace 

int isSet = (int) i &  1 << j;
if (isSet > 0) {
    // if yes, set the corresponding jth bit of x as 1.
}

by: 

if (0!=(int) i &  1 << j) {
    // if yes, set the corresponding jth bit of x as 1.
}

except if you need the variable isSet somewhere else again.

Regarding Gray Code: This would minimize the number of bit changes, but I cannot see how that could improve the generation of all sub sets, But Gray Code is useful, if you are interested in an order of sub sets which have the characteristic that they differ only in one element while iterating through them.

Upvotes: 2

Related Questions