C++ এ একটি স্ট্রিংয়ের সমস্ত প্যালিনড্রোম পারমুটেশন প্রিন্ট করুন

এই সমস্যায়, আমাদের একটি স্ট্রিং দেওয়া হয়েছে এবং আমাদের সেই স্ট্রিংটির অক্ষর থেকে সম্ভাব্য সমস্ত প্যালিনড্রোমিক পারমুটেশনগুলি প্রিন্ট করতে হবে৷

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক -

ইনপুট −৷ স্ট্রিং ='aabb'

আউটপুট - আব্বা বাব

এই সমস্যাটি সমাধান করার জন্য আমাদের স্ট্রিংয়ের অক্ষরগুলি নিতে হবে এবং এই অক্ষরগুলি ব্যবহার করে একের পর এক সমস্ত প্যালিনড্রোম স্ট্রিং তৈরি করতে হবে৷

ধাপ 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