Itération sur des sous-ensembles de toute taille

Je peux parcourir les sous-ensembles de taille 1

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

ou sous-ensembles de taille 2

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

ou 3

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

Mais comment faire cela pour des sous-ensembles de taille n?

Cela fait le travail, basé sur une réponse de Adam Rosenfield

 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); } } 

Vous pouvez utiliser la récursivité:

 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); 

Vous pourriez probablement faire cela avec une certaine récursivité.

Voici quelque chose que j’ai utilisé pour un problème similaire. Il n’utilise pas de récursivité; au lieu de cela, il utilise un vecteur d’index.

 #include  template class MultiForVar { std::vector _begin, _end, _vars; inline int dim(){return _vars.size();} public: MultiForVar(std::vector begin, std::vector end) : _begin(begin), _end(end), _vars(_begin) { assert(begin.size() == end.size() and "Starting and ending vector 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& getRaw(){ return _vars; } 

};

Si je comprends bien ce que vous demandez, une autre façon de le faire est d’utiliser des opérateurs par bits:

 for(int i = 0; i < 1< 

Vous avez besoin de quelque chose qui construit le pouvoir de l’ensemble original. Cela fait longtemps que je n’ai pas écrit cela, mais le psuedocode ressemble à

 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) }