Iterating over subsets of any size

Question

I can iterate over the 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?

This does the job, based on an answer by 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);
    }
}

I don't suppose you would add a few more comments to your answer? I'm clearly being slow but I'm not really following it. — Jekowl, Aug 02 '15 at 11:18

score 7 · Accepted Answer · answered Nov 05 '09 at 20:15

7

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

answered Nov 05 '09 at 20:15

Adam Rosenfield

390,455
97
512
589

This is interesting. However a[i] > a[j] where i>j is not enforced – ravenspoint Nov 05 '09 at 20:25
But if I add this: int start = 0; if( i > 0 ) start = a[i-1]; for(a[i] = start; a[i] < size; a[i]++) – ravenspoint Nov 05 '09 at 20:27
Oops! Should be int start = 0; if( i > 0 ) start = a[i-1]+1; for(a[i] = start; a[i] < size; a[i]++) – ravenspoint Nov 05 '09 at 20:30
One more change needed. The for loop maximum should be n, rather than size. With these changes, the algorithm works in production code and passes unit tests! Thanks. – ravenspoint Nov 05 '09 at 21:15

score 1 · Answer 2 · answered Nov 05 '09 at 21:56

Here is something I used for a similar problem. It does not use recursion; rather, it uses a vector of indexes.

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

};

score 1 · Answer 3 · answered Nov 05 '09 at 23:17

1

If I understand what you're asking correctly, another way to do it is to use bit-wise 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");
}

answered Nov 05 '09 at 23:17

Soufiane Hassou

17,257
2
39
75

score 1 · Answer 4 · answered Nov 05 '09 at 23:36

You need something the constructs the powerset of the original set. It's been a while since I've written that, but the 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)
}

Iterating over subsets of any size

4 Answers4

Linked