এই সমস্যায়, আমাদের n আকারের একটি স্ট্রিং দেওয়া হয়। এবং আমাদের সমস্ত সম্ভাব্য প্যালিনড্রোমিক পারমুটেশন মুদ্রণ করতে হবে যা বর্ণানুক্রমিক ক্রমে স্ট্রিং এর অক্ষর ব্যবহার করে তৈরি করা যেতে পারে। যদি স্ট্রিং প্রিন্ট '-1' ব্যবহার করে প্যালিনড্রোম তৈরি না হয়।
বিষয়টি আরও ভালোভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক -
Input: string = “abcba” Output : abcba bacba
এখন, এটি সমাধান করার জন্য আমাদের সম্ভাব্য সমস্ত প্যালিন্ড্রোম খুঁজে বের করতে হবে এবং তারপর সেগুলিকে বর্ণানুক্রমিক ক্রমে (লেক্সিকোগ্রাফিক্যাল ক্রম) সাজাতে হবে। অথবা অন্য উপায় হতে পারে আভিধানিকভাবে প্রথম প্যালিনড্রোম খুঁজে বের করা যা স্ট্রিং থেকে তৈরি। তারপর ক্রমানুসারে পরবর্তী প্যালিনড্রোমটি সন্ধান করুন।
এর জন্য, আমরা নিম্নলিখিত পদক্ষেপগুলি করব -
ধাপ 1 − স্ট্রিং এর সমস্ত অক্ষরের সংঘটনের ফ্রিকোয়েন্সি সংরক্ষণ করুন।
ধাপ 2 - এখন স্ট্রিং একটি প্যালিনড্রোম গঠন করতে পারে কিনা তা পরীক্ষা করুন। যদি প্রিন্ট না হয় "কোন প্যালিনড্রোম গঠন করা যাবে না" এবং প্রস্থান করুন। অন্যথায় করুন -
ধাপ 3 − যুক্তির উপর ভিত্তি করে একটি স্ট্রিং তৈরি করুন যাতে জোড় ঘটনা সহ সমস্ত অক্ষর অন্যদের থেকে একটি স্ট্রিং এবং বিজোড় ঘটনা তৈরি করে। এবং আমরা জোড় স্ট্রিং এর মধ্যে বিজোড় স্ট্রিং স্যান্ডউইচ করব (অর্থাৎ even_string + odd_string + even_string আকারে)।
এটি ব্যবহার করে আমরা অভিধানিকভাবে প্রথম প্যালিনড্রোম খুঁজে পেতে পারি। তারপর সমসাময়িক লেক্সিকোগ্রাফিক্যাল কম্বিনেশন চেক করে পরবর্তীটি খুঁজুন।
উদাহরণ
ধারণাটি ব্যাখ্যা করার জন্য প্রোগ্রাম -
#include <iostream>
#include <string.h>
using namespace std;
const char MAX_CHAR = 26;
void countFreq(char str[], int freq[], int n){
for (int i = 0; i < n; i++)
freq[str[i] - 'a']++;
}
bool canMakePalindrome(int freq[], int n){
int count_odd = 0;
for (int i = 0; i < 26; i++)
if (freq[i] % 2 != 0)
count_odd++;
if (n % 2 == 0) {
if (count_odd > 0)
return false;
else
return true;
}
if (count_odd != 1)
return false;
return true;
}
bool isPalimdrome(char str[], int n){
int freq[26] = { 0 };
countFreq(str, freq, n);
if (!canMakePalindrome(freq, n))
return false;
char odd_char;
for (int i = 0; i < 26; i++) {
if (freq[i] % 2 != 0) {
freq[i]--;
odd_char = (char)(i + 'a');
break;
}
}
int front_index = 0, rear_index = n - 1;
for (int i = 0; i < 26; i++) {
if (freq[i] != 0) {
char ch = (char)(i + 'a');
for (int j = 1; j <= freq[i] / 2; j++) {
str[front_index++] = ch;
str[rear_index--] = ch;
}
}
}
if (front_index == rear_index)
str[front_index] = odd_char;
return true;
}
void reverse(char str[], int i, int j){
while (i < j) {
swap(str[i], str[j]);
i++;
j--;
}
}
bool nextPalindrome(char str[], int n){
if (n <= 3)
return false;
int mid = n / 2 - 1;
int i, j;
for (i = mid - 1; i >= 0; i--)
if (str[i] < str[i + 1])
break;
if (i < 0)
return false;
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (str[j] > str[i] && str[j] < str[smallest])
smallest = j;
swap(str[i], str[smallest]);
swap(str[n - i - 1], str[n - smallest - 1]);
reverse(str, i + 1, mid);
if (n % 2 == 0)
reverse(str, mid + 1, n - i - 2);
else
reverse(str, mid + 2, n - i - 2);
return true;
}
void printAllPalindromes(char str[], int n){
if (!(isPalimdrome(str, n))) {
cout<<"-1";
return;
}
do {
cout<<str<<endl;
} while (nextPalindrome(str, n));
}
int main(){
char str[] = "abccba";
int n = strlen(str);
cout<<”The list of palindromes possible is :\n”;
printAllPalindromes(str, n);
return 0;
} আউটপুট
সম্ভাব্য প্যালিনড্রোমের তালিকা হল −
abccba acbbca baccab bcaacb cabbac cbaabc
