C++で文字列のすべての回文順列をアルファベット順に出力する方法

問題の概要

この問題では、長さnの文字列が与えられます。その文字列に含まれる文字を使って生成できるすべての回文（パリンドローム）の順列を、アルファベット順（辞書順）に出力することが求められます。もし回文を構成できない場合は「-1」を出力してください。

具体例を見てみましょう。

入力:
string = "abcba"

出力:
abcba
bacab

「abcba」の場合、文字の出現頻度は a:2、b:2、c:1 となり、前半部分を「ab」「ba」と入れ替えた2つの回文が作れます。

解決のためのアプローチ

この問題を解くには、まず作成可能なすべての回文を見つけ、それらを辞書順に並べ替える必要があります。より効率的な方法としては、文字列から作れる辞書順で最初の回文を見つけ、その後、順次「次の回文」を求めていくというアプローチがあります。

アルゴリズムの手順

ステップ1 − 文字列内の各文字の出現頻度をカウントします。

ステップ2 − その文字列から回文を構成できるかどうかを判定します。構成できない場合は「回文を作成できません」と出力して終了します。構成できる場合は次のステップへ進みます。

ステップ3 − 偶数回出現する文字で前半部分を構成し、奇数回出現する文字は中央に配置するというルールに基づいて文字列を組み立てます。具体的には「前半部分 ＋ 中央の奇数文字 ＋ 前半部分の逆順」という形式になります。

この手法により、辞書順で最初の回文を得ることができます。その後、隣接する辞書順の組み合わせを順に調べることで、次々と回文を生成していきます。

C++での実装例

上記の概念を示すサンプルプログラムです。

#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

計算量について

回文の判定と最初の回文の構築にはO(n)の時間がかかります。「次の回文」の生成も前半部分のみを操作するため高速に行え、全体の計算量はO(k × n)となります（kは生成される回文の総数）。全順列を生成して回文かどうかを毎回チェックする非効率な方法（O(n!)）と比べて、大幅な高速化が実現できます。