C++で順列リストから欠けている順列を見つける方法

問題概要

ある単語の順列(並べ替え)のうち、いくつかがリストとして与えられます。本来存在するはずの順列のうち、このリストに含まれていない「欠けている順列」をすべて見つけるのが本記事の目的です。

例

順列リスト = { "ABC", "ACB", "BAC", "BCA" } の場合、
欠けている順列は { "CAB", "CBA" } となります

アルゴリズム

• 与えられた文字列をすべて集合(std::set)に格納する
• 考えられるすべての順列を生成し、もう一つの集合を作る
• 2つの集合の差分を計算して返す

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void findMissingPermutation(string givenPermutation[], size_t
permutationSize) {
    vector<string> permutations;
    string input = givenPermutation[0];
    permutations.push_back(input);
    while (true) {
        string p = permutations.back();
        next_permutation(p.begin(), p.end());
        if (p == permutations.front())
            break;
        permutations.push_back(p);
    }
    vector<string> missing;
    set<string> givenPermutations(givenPermutation,
    givenPermutation + permutationSize);
    set_difference(permutations.begin(), permutations.end(),
        givenPermutations.begin(),
        givenPermutations.end(),
        back_inserter(missing));
    cout << "Missing permutations are" << endl;
    for (auto i = missing.begin(); i != missing.end(); ++i)
        cout << *i << endl;
}
int main() {
    string givenPermutation[] = {"ABC", "ACB", "BAC", "BCA"};
    size_t permutationSize = sizeof(givenPermutation) / sizeof(*givenPermutation);
    findMissingPermutation(givenPermutation, permutationSize);
    return 0;
}

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

出力

Missing permutations are
CAB
CBA

コードの解説

findMissingPermutation 関数では、まず入力配列の先頭要素を基準にして std::next_permutation を繰り返し呼び出すことで、その文字列から作れるすべての順列を辞書順に生成しています。生成された順列が先頭の文字列に戻った時点でループを終了します。なお、この方法が正しく機能するためには、初期文字列が昇順にソートされている必要がある点に注意してください。

次に、与えられた順列を std::set に格納し、std::set_difference を使って「全順列の集合」から「与えられた順列の集合」を引いた差分、すなわち欠けている順列だけを抽出して出力します。

この手法の計算量は、順列の総数が n!(n は文字数)に比例するため、文字数が増えると急激に大きくなります。長い文字列を扱う場合は、各文字の出現回数を集計して比較するなど、より効率的なアプローチを検討するとよいでしょう。