Recursive for-loop for Mastermind algorithm in C++

Question

I want to create a pool of numbers for an Mastermind algorithm (https://www.swtestacademy.com/algorithms-mastermind/). The pool should consist of every possible combination of an Mastermind code with size n. So for example when n = 4 the pool should look like this:

[0000][0001][0002] .... [5555]

with n = 5:

[00000] .... [55555]

where every number represents a color from the mastermind solution. So for Example [3101] would be red,blue,white,blue.

I made a function to create a pool with n = 4:

vector<string> createPool4()
{
    vector<string> pool;

    for (int i = 0; i < colours; i++)
        for (int j = 0; j < colours; j++)
            for (int k = 0; k < colours; k++)
                for (int l = 0; l < colours; l++)
                    pool.push_back(to_string(i) + to_string(j) + to_string(k) + to_string(l));

    return pool;
}

What i tried then, was to transform this function into some kind of recursive nested for-loop but, well look for yourself:

vector<string> fillPool(int n, vector<string> pool, const string& s) {

    if (n == 0) {
        pool.push_back(s);
        s.clear();
        return pool;

    }

    for (int i = 0; i < n; i++) {
        s += to_string(i);
        pool = fillPool(n-1,pool,s);
    }
}

This Code doesn't work, it should just show in what directions I was going.

So to conclude, I need a function that can take a dimension n and then create a list of possible codes. so far i was going with a vector of strings but I'm happy to hear alternative possibilities.

Maybe someone can help me with this, because I know that somewhere out there, there is a really good solution for this.

Thanks!

You use pool as input and overwrite it with the result ... If this is not optimized in a cool way you have a lot of copies of pool. Maybe it would be better to have a reference to pool to modify. — , Mar 19 '20 at 10:06
I do not see the point to make `s` a const reference. You are modifing the string (by adding another character) so it is not a const reference. I think you should take it by value. — , Mar 19 '20 at 10:13

score 0 · Accepted Answer · answered Mar 19 '20 at 18:48

This can be solved using combinations and permutations.

The idea is to:

create all the possible combinations for a given n and numberOfColours.
create all the different permutations for each combination, append it to the combinations and then remove any duplicates.

This question has some good answers on how to do the combinations. Putting together this solution and this solution from Rosetta code for the combination and permutation respectively, the problem can be solved this way:

#include <algorithm>
#include <iostream>
#include <memory>
#include <string>
#include <vector>

using namespace std;

void permutation(string str, vector<string> *result) {
  auto strCopy = str;
  std::sort(str.begin(), str.end());
  do {
    result->push_back(str);
  } while (std::next_permutation(str.begin(), str.end()));

  // To avoid duplication 
  result->erase(std::remove(result->begin(), result->end(), strCopy), result->end());
}

void combination(int n, int numberOfColours, vector<string> *result) {
  vector<string> colours;
  for (int i = 0; i < numberOfColours; i++)
    colours.push_back(to_string(i));
  auto s = colours.size() - 1;
  vector<int> v(n + 1, 0);
  while (true) {
    for (int i = 0; i < n; ++i) {
      if (v[i] > s) {
        v[i + 1] += 1;
        for (int k = i; k >= 0; --k) {
          v[k] = v[i + 1];
        }
      }
    }

    if (v[n] > 0)
      break;
    string str{};
    for (size_t i = 0; i < n; ++i)
      str.append(colours[v[i]]);
    result->push_back(str);
    v[0] += 1;
  }
}

void createPoolN(int n, int numberOfColours, vector<string> *pool) {
  combination(n, numberOfColours, pool);
  auto perms = make_unique<vector<string>>();
  for (const auto &p : *pool) {
    permutation(p, perms.get());
  }
  pool->insert(pool->end(), perms->begin(), perms->end());
  sort(pool->begin(), pool->end());
}

int main() {
  int n = 5;
  int numberOfColours = 10;
  auto pool = make_unique<vector<string>>();
  createPoolN(n, numberOfColours, pool.get());
  for (const auto &p : *pool)
    cout << "[" << p << "]\n";
  return 0;
}

Output:

[00000]
[00001]
[00002]
...
[99997]
[99998]
[99999]

Recursive for-loop for Mastermind algorithm in C++

1 Answers1