【C++】文字列から作れるすべての回文順列を出力する方法

問題概要

この問題では、与えられた文字列を構成する文字を使って作成できるすべての回文（前から読んでも後ろから読んでも同じになる文字列）の順列をすべて出力します。

具体例で理解しよう

入力： string = "aabb"

出力：

abba
baab

この問題を解くには、文字列の各文字を取り出し、それらを使って回文となる文字列を1つずつ生成していく必要があります。

解法アルゴリズム

以下の手順で回文順列を効率的に生成できます。

ステップ1： その文字列から回文が作れるかどうかを判定します。作れない場合は「Not Possible」を出力します。
ステップ2： 回文が作れる場合、文字列を半分に分け、各文字を辞書順に選択していきます。
ステップ3： 生成した半分の文字列の順列を走査し、偶数長の場合は半分を反転させて結合します。奇数回出現する文字がある場合は、その文字が中央に来るように配置して回文を作ります。
ステップ4： 生成されたすべての回文を出力します。

実装プログラム

上記のアルゴリズムを実装したC++のコード例です。

#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

アルゴリズムのポイント

回文が成立する条件は、各文字の出現回数がすべて偶数であること（偶数長の場合）、または1つの文字だけ奇数回出現すること（奇数長の場合）です。この性質を利用して事前に回文の可否を判定することで、無駄な探索を省き、効率的にすべての回文順列を生成できます。また、next_permutation を使うことで、半分の文字列の順列を辞書順に列挙でき、結果も自然にソートされた形で得られます。