0

Hi all there.

I was given the task to implement a Subset class with a few function.

It should be structured so to contain the original set and make it possible to generate all subsets.

Right now I'm focusing on the "generate all subsets" part.

I've done a little searching and I thought to implement it as an array (the original set) and a bitmask to indicate what elements are present in the current subset. That idea came to me from a Java forum (I hope I understood it correctly since I'm not into Java at all).

As of now it works fine, only it seems to me a little slow... any suggestion on how to optimize it? I'm open to different approaches as well.

Here's the (relevant) code:

```
// subset.h
#include <iostream>
#ifndef H_SUBSET
#define H_SUBSET
template <class T>
class Subset {
private:
int Dimension;
T *Set;
bool *Bitmask;
public:
Subset(T *set, int dim);
~Subset(void);
void Show(void);
void NextSubset(void);
void EmptySet(void);
void FullSet(void);
int Cardinality(void);
T operator[](int index);
};
// ... other (not relevant) functions
template <class T>
void Subset<T>::NextSubset(void) {
int i = Dimension - 1;
while(!Bitmask[i]&&i>=0) {
i--;
}
if(i>=0) {
Bitmask[i] = !Bitmask[i];
}
for(int j = i+1; j < Dimension; j++) {
Bitmask[j] = !Bitmask[j];
}
return;
}
#endif // H_SUBSET
```

```
// main.cpp
#include "subset.h"
#define N 5
using std::cout;
using std::endl;
int main(void) {
char a[N];
for(int i = 0; i < N; i++) {
a[i] = 'a' + i;
}
Subset<char> mySubset(a, N);
for(int i = 0; i < (1 << N); i++) {
cout << endl;
mySubset.Show();
mySubset.NextSubset();
}
return 0;
}
```

Some timing:

```
N = 5 --> 0m0.004s
N = 10 --> 0m0.036s
N = 15 --> 0m3.570s
N = 20 --> 5m16s
```

Thanks for your time :)