cartesian product - Creating all possible combinations by taking k no: of items from an array with n no: of items in C++

Question

I'm looking for a way to insert an array with length n and get all possible combinations with length k. The elements can repeat.

If the no: of elements in the array = n and the sample size = k, the no: of possible combinations should be (n)^k.

---

For example if the array is [a,b,c] and k=2, then the possible combinations should be aa,ab,ac,bb,ba,bc,cc,ca,cb. The no: of combinations will be (3)^2=9

---

1. How do I create a dynamic array with the function std::vector
2. How do I get all the possible combinations?

I'm new to programming and hope you can explain a bit. Thanks in advance!

question from:https://stackoverflow.com/questions/65931570/creating-all-possible-combinations-by-taking-k-no-of-items-from-an-array-with-n

Answer 1

A hard code solution would be:

for (int a1 : v) {
  for (int a2 : v) {
    for (int a3 : v) {
      for (int a4 : v) {
        for (int a5 : v) {
            do_job(a1, a2, a3, a4, a5);
        }
      }
    }
  }
}

You may use the following for a generic way (putting all as into vector):

bool increase(std::size_t n, std::vector<std::size_t>& its)
{
    for (auto rit = its.rbegin(); rit != its.rend(); ++rit) {
        ++*rit;
        if (*rit >= n) {
            *rit = 0;
        } else {
            return true;
        }
    }
    return false;
}

template <typename F, typename C>
void iterate(F f, const C& v, std::size_t k)
{
    std::vector<std::size_t> it(k, 0);
 
    do {
        f(v, it);
    } while (increase(v.size(), it));
}

Live Demo