C++で重複を含む文字列のソート済み・重複なし順列を出力する方法

問題概要

本記事では、C++を用いて「与えられた文字列から作成できる、重複のないソート済み順列（distinct sorted permutations）をすべて出力する」というプログラミング問題を解説します。この問題には、次の2つの条件があります。

• 文字列には、同じ文字が複数回現れる場合がある（重複あり）。
• 入力される文字列は、あらかじめソートされた順序で与えられる。

具体的なイメージをつかむために、入出力の例を見てみましょう。

入力 : ABD
出力 : ABD, ADB, BAD, BDA, DAB, DBA

入力 : RSTU
出力 : RSTU, RSUT, RTSU, RTUS, RUST, RUTS, SRTU, SRUT, STRU, STUR, SURT, SUTR, TRSU, TRUS, TSRU, TSUR, TURS, TUSR, URST, URTS, USRT, USTR, UTRS, UTSR

順列（パーミュテーション）とは

順列（permutation）とは、集合に含まれるすべての要素を、特定の順序や規則に基づいて並べ替えることを指します。対象となる集合が整列されていても、いなくても構いません。

解法の考え方

まず、順列に関する基本的な数学的公式をおさらいしておきましょう。

• 相異なる n 個の文字からなる文字列から生成できる順列の総数は、n! 通りです。
• 文字列内に重複する文字が含まれる場合は、n! / i! 通りになります（i は各文字の重複回数）。

たとえば文字列「STURS」の場合、S が2回現れているため、生成できる文字列の総数は 5! / 2! = 60 通りとなります。

総数がわかったところで、実際に順列を生成する手順を見ていきましょう。

1. 文字列がソートされていない場合は、最初にソートしておきます（本問題では入力がすでにソート済みのため不要）。これにより、最終的な出力もソートされた順序になります。
2. 文字列の最初の文字を固定し、残りの文字の順列を再帰的に求めます。
3. 同様に、2番目以降の文字も順番に固定しながら処理を繰り返します。

この手法により、求めるべきすべての順列をソートされた形で得ることができます。

具体例

入力： RST

この文字列からは、合計 3! = 6 通りの順列が作成できます。

• R を固定すると、S と T の順列から RST、RTS の2通りが得られます。
• S を固定すると、SRT、STR の2通り。
• T を固定すると、TRS、TSR の2通り。

したがって、出力は RST, RTS, SRT, STR, TRS, TSR となり、ソートされた順序で並んでいることが確認できます。

C++での実装例

それでは、この問題を解くプログラムを作成してみましょう。ポイントは、文字を入れ替える前に同一文字がすでに使用されていないかをチェックする関数（swaper）を用意し、重複する順列の生成を防いでいる点です。

#include <bits/stdc++.h>
using namespace std;
// 重複する交換を防ぐためのチェック関数
bool swaper(char str[], int start, int curr){
    for (int i = start; i < curr; i++)
        if (str[i] == str[curr])
            return 0;
    return 1;
}
// 順列を再帰的に生成して出力する関数
void printPermutations(char str[], int index, int n){
    if (index >= n) {
        cout<<str<<"\t";
        return;
    }
    for (int i = index; i < n; i++) {
        bool check = swaper(str, index, i);
        if (check) {
            swap(str[index], str[i]);
            printPermutations(str, index + 1, n);
            swap(str[index], str[i]); // 元に戻す（バックトラック）
        }
    }
}
int main(){
    char str[] = "AABC";
    int n = strlen(str);
    cout<<"The string is : "<<str<<endl;
    cout<<"The distinct sorted permutations are : \t";
    printPermutations(str, 0, n);
    return 0;
}

実行結果

The string is : AABC
The distinct sorted permutations are : AABC AACB ABAC ABCA ACBA ACAB BAAC BACA BCAA CABA CAAB CBAA

コードの解説

このプログラムの動作を簡単に整理してみます。

• swaper関数： 現在の位置より前に同じ文字が存在するかどうかを確認します。同じ文字が見つかった場合は交換を行わず、重複する順列が生成されるのを防ぎます。
• printPermutations関数： 再帰呼び出しによって順列を生成します。インデックスが文字列長に達した時点で、完成した1つの順列を出力します。
• バックトラック： 再帰から戻った後に文字を元の位置へ戻すことで、次の組み合わせを正しく試行できるようにしています。

入力文字列「AABC」には A が2つ含まれるため、理論上の順列の総数は 4! / 2! = 12 通りとなり、実行結果でもちょうど12個の重複なし順列が出力されていることがわかります。

まとめ

重複文字を含む文字列から重複のない順列を生成するには、「同一文字の重複チェック＋再帰とバックトラックによる文字交換」が有効なアプローチです。あらかじめ文字列をソートしておくことで、出力も整然とした順序になり、アルゴリズムの理解もしやすくなります。順列の総数を n! や n!/i! で事前に計算しておけば、プログラムの出力結果が正しいかどうかの検証にも役立ちます。