БлогNot. Наилучшее перемешивание символов в строке

Наилучшее перемешивание символов в строке

Очевидно, целью такого перемешивания может быть расстановка наибольшего количества символов строки не на своих исходных позициях. Это не всегда возможно для всех символов, если в строке есть повторы, также задача не всегда решается единственным образом (для "pop" получится "opp" или "ppo").

В коде, который запускался из консоли Visual Studio 2019, используются стандартный алгоритм shuffle и генератор псевдослучайных чисел Mersenne Twister 19937 generator.

Ниже приводится листинг программы и результаты тестирования. Перемешивание реализовано как шаблон класса.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <random>

using namespace std;

template <class S> class BestShuffle {
public:
 BestShuffle() : randDevice(), randGen(randDevice()) {}

 S operator()(const S& s1) {
  S s2 = s1;
  shuffle(s2.begin(), s2.end(), randGen);
  for (unsigned i = 0; i < s2.length(); i++)
   if (s2[i] == s1[i])
    for (unsigned j = 0; j < s2.length(); j++)
     if (s2[i] != s2[j] && s2[i] != s1[j] && s2[j] != s1[i]) {
      swap(s2[i], s2[j]);
      break;
     }
  ostringstream os;
  os << s1 << endl << s2 << " [" << count(s2, s1) << ']';
  return os.str();
 }

private:
 static int count(const S& s1, const S& s2) {
  unsigned count = 0;
  for (unsigned i = 0; i < s1.length(); i++) if (s1[i] == s2[i]) count++;
  return count;
 }

 random_device randDevice;
 mt19937 randGen;
};

int main () {
 BestShuffle <basic_string<char>> bs;
 basic_string <char> tests[] = {"abracadabra","megaplus","pop"};
 unsigned size = sizeof(tests)/ sizeof(tests[0]);
 for (unsigned i = 0; i < size; i++)
  cout << bs(basic_string<char>(tests[i])) << endl;
 return 0;
}
abracadabra
daababarrac [0]
megaplus
laeugmsp [0]
pop
ppo [1]

теги: textprocessing алгоритм random c++

10.11.2020, 13:15; рейтинг: 59