Combinatorial Generators

[Guest]

Hi,
can any one tell me an algorithm on how to make combinatorial generators?
for example i need to generate all possible subsets from a given string, order is not important:
"abc"
should generate
"a","b","c","ab","ac",bc"

i know that there is a function called next_permutation() in c++, but how to write a combinatorial generator as next_combinatorial(), so i can call it in a while() loop.

thanks alot

[Colonel Kernel]

This sounds a bit like a homework question to me, so I will keep my answer very short:

• Use recursion (at least when designing the algorithm).
• I have no idea what next_permutation() function you're talking about.
• Once you've finished the code, expect it to run very slowly on large input sets.

[Guest]

I'm not a student or related to CS studing anyway, i just compete in topcoder competitions and i found my self in a need to such a function.

For next_permutation() its available in algorithm header file

u can do this:

string s;
s.resize(3);
s[0]='a';
s[1]='b';
s[2]='c';
do
{
cout << s << endl;
}while(next_permutation(s.begin(), s.end());

which is self explaining

[Kevin McGuire]

#define SET    "abc"

int main(int argc, char *argv[]){
   char *set = SET;
   unsigned int wheel = 0, bit, pos;
   for(; wheel < pow(2, strlen(SET)); ++wheel){
      for(bit = 1, pos = 0; bit < pow(2, strlen(SET)); bit = bit * 2, ++pos){
         if((bit & wheel) == bit){
            printf("%c", set[pos]);
         }
      }
      printf("\n");
   }
}