指定された文字列のすべての回文順列をC++でアルファベット順に印刷します

この問題では、サイズnの文字列が与えられます。また、文字列の文字をアルファベット順に使用して生成できるすべての可能な回文順列を印刷する必要があります。文字列印刷「-1」を使用して回文が作成されていない場合。

トピックをよりよく理解するために例を見てみましょう-

Input:
string = “abcba”
Output :
abcba
bacba

ここで、これを解決するには、可能なすべての回文を見つけて、アルファベット順に（辞書式順序）並べる必要があります。または、別の方法は、文字列から作成された辞書式順序で最初の回文を見つけることです。次に、シーケンスの次の回文を順番に見つけます。

このために、次の手順を実行します-

ステップ1 −文字列のすべての文字の出現頻度を保存します。

ステップ2 −次に、弦が回文を形成できるかどうかを確認します。 PRINTがない場合は、「パリンドロームを形成できません」と終了します。それ以外の場合は-

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