fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. #include <algorithm>
  5. #include <vector>
  6. #include <unordered_map>
  7.  
  8.     unordered_map<int, int> count_letters(string & s) {
  9.         unordered_map<int, int> counter;
  10.         for (auto & letter : s) {
  11.             counter[letter] += 1;
  12.         }
  13.         return counter;
  14.     }
  15.  
  16.     int get_cnt_even(unordered_map<int, int> & counter) {
  17.         int cnt_even = 0;
  18.         for (auto it = counter.begin(); it != counter.end(); ++it) {
  19.             cout << "letter " << it->first << " " << it->second << " " << it->second % 2 << endl;
  20.             if (it->second % 2 == 1) {
  21.                 cnt_even += 1;
  22.             }
  23.         }
  24.         return cnt_even;
  25.     }
  26.  
  27.     string get_all_possible_letters(unordered_map<int, int> & counter) {
  28.         char even_char = '\0';
  29.  
  30.         string letters;
  31.         for (auto it = counter.begin(); it != counter.end(); ++it) {
  32.             for (int i = 0; i < it->second / 2; ++i) {
  33.                 letters += it->first;
  34.             }
  35.  
  36.             if (it->second % 2 == 1) {
  37.                 even_char = it->first;
  38.             }
  39.         }
  40.  
  41.         if (even_char != '\0') {
  42.             letters.push_back(even_char);
  43.         }
  44.  
  45.         return letters;
  46.     }
  47.  
  48.     void generate_permutations(string & cur_string, string & letters_to_add, vector<string> & answers) {
  49.         if (letters_to_add.empty()) {
  50.             answers.push_back(cur_string);
  51.         }
  52.  
  53.         int value = '\0'; // to don't coinside with nums[0]
  54.         for (int i = 0; i < letters_to_add.size(); ++i) {
  55.             if (value == letters_to_add[i]) {
  56.                 continue;
  57.             }
  58.  
  59.             cur_string.push_back(letters_to_add[i]);
  60.             // delete from i-th position
  61.             value = letters_to_add[i];
  62.             letters_to_add.erase(letters_to_add.begin() + i);
  63.  
  64.             generate_permutations(cur_string, letters_to_add, answers);
  65.  
  66.             // insert (return) to i-th position
  67.             letters_to_add.insert(letters_to_add.begin() + i, cur_string.back());
  68.             cur_string.pop_back();
  69.         }
  70.     }
  71.  
  72.     void mirror_strings(vector<string> & answers, char even_char = '\0') {
  73.         for (auto & str : answers) {
  74.             auto reversed_tail = str;
  75.             reverse(reversed_tail.begin(), reversed_tail.end());
  76.             if (even_char != '\0') {
  77.                 str += even_char;
  78.             }
  79.             str += reversed_tail;
  80.         }
  81.     }
  82.  
  83.     vector<string> generatePalindromes(string s) {
  84.         if (s.size() == 1) {
  85.             return {s};
  86.         }
  87.  
  88.         auto counter = count_letters(s);
  89.         int cnt_even = get_cnt_even(counter);
  90.         if (s.empty() || cnt_even > 1) {
  91.             return {};
  92.         }
  93.         cout << "cnt_even = " << cnt_even << endl;
  94.  
  95.         string start_letters = get_all_possible_letters(counter);
  96.         char even_char = '\0';
  97.         if (cnt_even == 1) {
  98.             even_char = start_letters[start_letters.size() - 1];
  99.             start_letters.pop_back();
  100.  
  101.             if (start_letters.empty()) {
  102.                 return {string(1, even_char)};
  103.             }
  104.         }
  105.  
  106.         cout << "start_letters : " << start_letters << endl;
  107.  
  108.         vector<string> answers;
  109.         string cur_string;
  110.         generate_permutations(cur_string, start_letters, answers);
  111.         mirror_strings(answers, even_char);
  112.         return answers;
  113.     }
  114.  
  115. int main() {
  116. 	for (auto v : generatePalindromes("abc")) {
  117. 		cout << v << endl;
  118. 	}
  119. 	return 0;
  120. }
Success #stdin #stdout 0s 4796KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
letter 99 1 1
letter 97 1 1
letter 98 1 1
https://ideone.com/oAkxyl
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!