combinations with repitition iterative

comb_with_rep_iter.cpp

#include <iostream>
#include <string>
#include <vector>

void print_vector(const std::vector<int> &pos,
                  const std::vector<std::string> &str) {
  for (size_t i = 1; i < pos.size(); ++i) // offset: i:1..N
    printf("%s\t", str[pos[i]].c_str());  // str:0..N-1
  printf("\n");
}

//asume caller initializes k+1 memory (0 byte for overflow to stop algorithm)
bool step_comb_with_rep(std::vector<int> &pos, int n)
{
  int k = pos.size()-1;
  pos[k] += 1; // xxxxN -> xxxxN+1
  for (int i = k; i > 0; i -= 1) {
    if (pos[i] > n - 1) // if number spilled over: xx0(n-1)xx
    {
      pos[i - 1] += 1; // set xx1(n-1)xx
      for (int j = i; j <= k; j += 1)
        pos[j] = pos[j - 1]; // set xx11..1
    }
  }
  if (pos[0] > 0) // stop condition: 1xxxx
      return false;
  return true;
}

// usage combination with repitition
int main() {
  std::vector<std::string> str{"iced", "jam", "plain"};
  int k= 2;
  int n = 3;
  std::vector<int> pos(k + 1, 0);
  std::cout << pos[0] << pos[1] << pos[2] << "\n";
  print_vector(pos, str);
  while (step_comb_with_rep(pos, n) == true)
  {
      std::cout << pos[0] << pos[1] << pos[2] << "\n";
      print_vector(pos, str);
  }
  return 0;
}