Перебор подмножеств любого размера

Question

я могу перебирать не подмножеств размера 1

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

или подмножества размером 2

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

или 3

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

Но как это сделать это для подмножеств размера n?

Это делает работу, основанную на ответ Адама Розенфельд

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

Вы можете использовать рекурсию:

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

Вы, вероятно, могли бы сделать это с некоторой рекурсией.

Answer 3

Вот что-то я использовал для подобной задачи. Он не использует рекурсию; скорее, он использует вектор индексов.

#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

Если я понимаю, что вы просите правильно, другой способ сделать это состоит в использовании битовых операторов:

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

Вам нужно что-то строит-powerset исходного множества. Прошло некоторое время с тех пор, как я это написал, но psuedocode выглядит как

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