Печатать все перестановки символов выбранной длины с повторением и не начинать заново после закрытия программы в CPP

Обработка перестановок строк

C++ имеет удобный алгоритм стандартной библиотеки std::next_permutation, который вы можете использовать для обработки перестановок строк.

Одно решение

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

После каждой итерации вы можете сохранить текущее состояние родительской перестановки. Позже вы можете передать его функции print_permutation, которая возобновит расчет перестановки с этой точки. См. реализацию ниже для более подробной информации.

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>

typedef std::function<void(const std::string& masterPerm, const bool finished)> PermutationCallback;

std::string new_master_permutation(std::string&& str) {
  std::sort(str.begin(), str.end());
  return str;
}

void print_permutation_if_unused(
  const std::string& childPermutation,
  std::unordered_set<std::string>& childPermsTried
) {
  if (!childPermsTried.contains(childPermutation)) {
    childPermsTried.insert(childPermutation);
    std::cout << childPermutation << '\n';
  }
}

void print_permutations(
  std::string masterPermutation,
  const size_t numCharsInPerm,
  const PermutationCallback& callback
) {
  std::unordered_set<std::string> childPermsTried;
  // Actual constrained length of child permutation strings
  const size_t permutationLength = std::min(masterPermutation.size(), numCharsInPerm);

  do {
    print_permutation_if_unused(masterPermutation.substr(0, permutationLength), childPermsTried);
    callback(masterPermutation, false);
  } while (std::next_permutation(masterPermutation.begin(), masterPermutation.end()));

  callback(masterPermutation, true);
}

int main(void) {
  // Begin with a new permutation, starting with the sorted string "abbc"
  print_permutations(new_master_permutation("bacb"), 3,
    [](const std::string& masterPerm, const bool finished) {
      // Save the master permutation for reference
    }
  );

  // Begin at any midpoint permutation ("bacb"), and calculate the rest.
  print_permutations("bacb", 3, [](const std::string& masterPerm, const bool finished) {
    // Save the master permutation for reference
  });
  return EXIT_SUCCESS;
}

Обратите внимание, что эта реализация далека от оптимальной. Выполнение увеличивается на факториальное время с каждым символом, добавляемым в основную строку перестановки. Большая длина дочерней перестановки значительно увеличивает использование памяти, поскольку каждая уникальная перестановка хранится в наборе. Тем не менее, это работает и должно стать как минимум хорошей отправной точкой.