文字列のすべての回文順列をC++で出力します

この問題では、文字列が与えられ、その文字列の文字から可能なすべての回文順列を印刷する必要があります。

問題を理解するために例を見てみましょう-

入力- string =‘aabb’

出力- アババーブ

この問題を解決するには、文字列の文字を取得し、これらの文字を使用してすべての回文文字列を1つずつ生成する必要があります。

ステップ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