Enumerating interactions between variables in a set

During my work for the University of Urbino, I recently needed to enumerate all interactions (or combinations to a certain maximum grade) between variables of a set. In other words, I needed to enumerate all possible subsets of a set, without repetition.

For instance, having a set of the following variables { A, B, C }, all interactions to the 3rd level are:

A
B
C
A, B
B, C
A, C
A, B, C

There probably are different solutions to the problem, but the one I ended implementing in C++ was the following:

VariableInteractions::VariableInteractions(const std::vector<std::string> &variables, int interactions){
  int n = (int)variables.size();

  //Rescale number of interactions, if too many
  if(interactions > n)
    interactions = n;
  
  //Scan all interactions
  for(int interaction = 1; interaction <= interactions; ++interaction){
    //As many positions as interactions
    int *positions = new int[interaction];
    for(int i = 0; i < interaction; ++i)
      positions[i] = i;

    int moving = interaction - 1;
    int standing = moving - 1;

    //Store first
    _interactions.push_back(VariableGroup(positions, interaction, variables));

    bool loop = true;
    do {
      //If moving element is blocked
      if(positions[moving] >= n - (interaction - moving)){
        //Seek the last element that can move
        int seek;
        for(seek = moving - 1; seek >= 0; --seek){
          //If 'seek' got space to move
          if(positions[seek + 1] - positions[seek] > 1)
            break;
        }

        //Break if no more moving parts (everybody on far right)
        if(seek > 0)
          break;

        moving = seek;

        //Move all elements in place (starting from positions[seek] + 1)
        int newMovingPos = positions[moving] + 1;
        for(int i = 0; (i + moving) 
          positions[i + moving] = newMovingPos + i;
        }

        moving = interaction - 1;
      }
      else{
        //Moving element is free to move
        positions[moving]++;
      }

      //Store
      _interactions.push_back(VariableGroup(positions, interaction, variables));
    }
    while(loop);

    //Clean up
    delete[] positions;
  }
}

The solution is based on a nice article I found, which explains the idea clearly: you have several "blocks" starting on the left end of your set. At each cycle one of the blocks will move right, giving you a new combination of variables that can be stored as an interaction. When one of the blocks cannot move further, you must reset it back, moving its left neighbor towards the right side of the set. This goes on until you have no more moves left and all blocks are aligned on the right side (check out the article for pictures of the process).

Another very smart solution is the following: simply create a binary vector of n elements (n being the number of elements in the set) and then enumerate all possible integer values that can be expressed by the vector. For instance:

And that's it: simply take each row and match it to the variables in your set. The first column would be A, the second B and the rightmost C. This gives you a very fast enumeration of all possible combinations of elements of the set, but you'll have to remove the ones you don't need (the most obvious one is the first row, which is simply the empty set) and those who have too many elements (if you want to limit the interactions of your variables to a certain grade).

Hope you find this useful.