Наилучшее перемешивание символов в строке
Очевидно, целью такого перемешивания может быть расстановка наибольшего количества символов строки не на своих исходных позициях. Это не всегда возможно для всех символов, если в строке есть повторы, также задача не всегда решается единственным образом (для "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]
10.11.2020, 13:15 [1091 просмотр]