C++에서 문자열의 모든 회문 순열 인쇄

이 문제에서 문자열이 주어지고 해당 문자열의 문자에서 가능한 모든 회문 순열을 인쇄해야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다 -

입력 - 문자열 ='abb'

출력 - 아바 바브

이 문제를 해결하려면 문자열의 문자를 가져와서 이 문자를 사용하여 모든 회문 문자열을 하나씩 생성해야 합니다.

1단계 − 문자열이 회문인지 확인하고 '불가능 인쇄 ' 그렇지 않은 경우.

2단계 − 회문을 만들 수 있으면 반으로 만들고 문자열의 각 문자를 사전순으로 선택합니다.

3단계 − 생성된 순열을 통과하고 짝수 길이 문자열과 홀수 주파수의 경우 반쪽을 반대로 하여 회문을 생성하려면 홀수 문자가 중간에 있어야 합니다.

4단계 - 생성된 모든 회문을 인쇄합니다.

알고리즘을 구현하는 프로그램 -

예

#include <bits/stdc++.h>
using namespace std;
#define M 26
bool isPalindrome(string str, int* freq){
   memset(freq, 0, M * sizeof(int));
   int l = str.length();
   for (int i = 0; i < l; i++)
      freq[str[i] - 'a']++;
   int odd = 0;
   for (int i = 0; i < M; i++)
      if (freq[i] % 2 == 1)
   odd++;
   if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))
      return true;
   else
      return false;
}
string reverse(string str){
   string rev = str;
   reverse(rev.begin(), rev.end());
   return rev;
}
void generatePalindromePermutation(string str){
   int freq[M];
   if (!isPalindrome(str, freq))
   return;
   int l = str.length();
   string half ="";
   char oddC;
   for (int i = 0; i < M; i++) {
      if(freq[i] % 2 == 1)
      oddC = i + 'a';
      half += string(freq[i] / 2, i + 'a');
   }
   string palindrome;
   do {
      palindrome = half;
      if (l % 2 == 1)
         palindrome += oddC;
      palindrome += reverse(half);
      cout<<palindrome<<endl;
   }
   while (next_permutation(half.begin(), half.end()));
}
int main() {
   string str="abab";
   cout<<"All palindrome permutations of "<<str<<" are :\n";
   generatePalindromePermutation(str);
   return 0;
}

출력

All palindrome permutations of abab are :
abba
baab