Iterating subsets of any size

Question

I can iterate through subsets of size 1

for( int a = 0; a < size; a++ ) { 

or subsets of size 2

 for( int a1 = 0; a1 < size; a1++ ) { for( int a2 = a1+1; a2 < size; a2++ ) { 

or 3

 for( int a1 = 0; a1 < size; a1++ ) { for( int a2 = a1+1; a2 < size; a2++ ) { for( int a3 = a2+1; a3 < size; a3++ ) { 

But how to do this for subsets of size n?

It does work based on Adam Rosenfield's answer

 void iterate(int *a, int i, int size, int n) { int start = 0; if( i > 0 ) start = a[i-1]+1; for(a[i] = start; a[i] < n; a[i]++) { if(i == n-1) { // a is the array of indices of size n for( int k = 0; k < size; k++ ) { printf("%d ",a[k]); } printf("\n"); } else iterate(a, i+1, size, n); } } 

Answer 1

You can use recursion:

 void iterate(int *a, int i, int size, int n) { for(a[i] = 0; a[i] < size; a[i]++) { if(i == n-1) DoStuff(a, n); // a is the array of indices of size n else iterate(a, i+1, size, n); } } ... // Equivalent to 4 nested for loops int a[4]; iterate(a, 0, size, 4); 

Answer 2

You can probably do this with some recursion.

Answer 3

Here is what I used for a similar problem. It does not use recursion; rather, it uses an index vector.

 #include <vector> template<class T> class MultiForVar { std::vector<T> _begin, _end, _vars; inline int dim(){return _vars.size();} public: MultiForVar(std::vector<T> begin, std::vector<T> end) : _begin(begin), _end(end), _vars(_begin) { assert(begin.size() == end.size() and "Starting and ending vector<T> not the same size!" ); } MultiForVar& operator ++() { ++_vars[dim()-1]; for(int d = dim()-1; d > 0; --d) { if( _vars[d] >= _end[d] ) { _vars[d] = _begin[d]; ++_vars[d-1]; } } return *this; } bool done() { /*for(int d = 0; d < dim(); ++d) if( _vars[d] < _end[d] ) return false; return true;*/ return (_vars[0] >= _end[0]); } T operator[](int d) { return _vars.at(d); } int numDimensions(){ return dim(); } std::vector<T>& getRaw(){ return _vars; } 

};

Answer 4

If I understand what you're asking correctly, another way to do this is to use bitwise operators:

 for(int i = 0; i < 1<<size; i++) { for(int j = 0; j < size; j++) { if(i & 1<<j) printf("%d ", a[j]); } printf("\n"); } 

Answer 5

You need something that creates the power plant of the original kit. It has been a long time since I wrote this, but psuedocode looks like

 Powerset(a, size) { if(size == 0) return emptyset subseta = Powerset(a, size-1) // Powerset of everything except last element subsetb = appendToAll(a[size-1], subseta) // appends the last element to every set in subseta return union(subseta, subsetb) }