Please help - generating subset

[Erik Anderson]

I have this program for generating subsets, I need to run it with input n=23. It has been running for the past 5 hours, is it normal???
Thank you!

/*generate subsets */

int subsets(vector < bool > sub, int i)
{


  if (i > n)
  {


    return 0;

  }


  else if (i == n)
  {


    for (int j = 0; j < n; j += 1)
    {

      cout << sub[j] << " ";



    }

    allSubsets.push_back(sub);

    cout << endl;


    return 1;

  }


  sub[i] = false;


  int a = subsets(sub, i + 1);



  sub[i] = true;


  int b = subsets(sub, i + 1);




  return a + b;



}

[Salem]

> I need to run it with input n=23. It has been running for the past 5 hours, is it normal???
I suggest you run it with

for ( n = 0 ; n < 15 ; n++ ) {
    // print the time
    // call subsets()
    // print the time
}

In other words, get a feel for the complexity of your program.

Say for example, n=12 takes 1 second, n=13 takes 2 seconds, n=14 takes 4 seconds (do you see where this is going, and what n=23 is going to take)?

[Cat]

Well, this looks like a highly inefficient program. If I'm reading it right, your goal is to find every permutation of 23 boolean variables?

1. Something this big probably shouldn't be recursive. To generate 2^23 vectors you make 2^24 -1 function calls, at least 2^24 (and probably over 2^25) copy constructions of vectors, etc. This could easily be a loop rather than a recursive function, and you can save yourself a massive amount of overhead.

2. To print all your permutations to console, you're writing somewhere in the neighborhood of 400 MB. That's a ton of data to dump to the console, which isn't a good way to display this volume of data. Is it really necessary?

3. You're essentially just storing every number from 0 to (2^23 - 1) except you're storing it in a very inefficient format. Why store that at all - anything you can do by looping over allSubsets you can do by looping over integers from 0 ... 0x7FFFFF and treating each bit as a boolean via bit shifting and masking.