Рекурсивный для-l oop для алгоритма Mastermind в C ++

Question

Я хочу создать пул чисел для алгоритма Mastermind (https://www.swtestacademy.com/algorithms-mastermind/). Пул должен состоять из всех возможных комбинаций кода Mastermind размером n . Так, например, когда n = 4 пул должен выглядеть следующим образом:

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

с n = 5 :

[00000] .... [55555]

, где каждое число представляет цвет из решения вдохновителя. Таким образом, для примера [3101] будет красный, синий, белый, синий.

Я создал функцию для создания пула с 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;
}

Тогда я попытался преобразовать эту функцию в рекурсивную вложенную форму для -l oop, но, посмотрите сами:

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

Этот код не работает, он должен просто отображаться в в каких направлениях я шел.

Итак, для завершения мне нужна функция, которая может взять измерение n, а затем создать список возможных кодов. пока я собирался использовать вектор строк, но я рад услышать альтернативные возможности.

Может быть, кто-то может мне помочь с этим, потому что я знаю, что где-то там есть действительно хорошее решение для этого .

Спасибо!

Answer 1

Это можно решить с помощью комбинаций и перестановок.

Идея состоит в том, чтобы:

1. создать все возможные комбинации для заданных n и numberOfColours.
2. создать все различные перестановки для каждой комбинации , добавьте его к комбинациям и затем удалите все дубликаты.

Этот вопрос содержит несколько хороших ответов о том, как делать комбинации. Собрав воедино это решение и это решение из кода Розетты для комбинации и перестановки соответственно, проблему можно решить следующим образом:

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

Вывод:

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