C++で最初のN個の数値の順列を昇順ソートするための最小プレフィックス反転回数

概要

1からNまでの数値の順列からなる長さNの配列が与えられます。1回の操作では、配列の任意のプレフィックス(先頭部分)を反転することができます。このとき、配列を昇順にソートするために必要な最小の操作回数を求めるのが課題です。

例

配列が {1, 2, 4, 3} の場合、昇順にソートするには最小で3ステップが必要です。

• 配列全体を反転 → {3, 4, 2, 1}
• 先頭の2要素を反転 → {4, 3, 2, 1}
• 配列全体を反転 → {1, 2, 3, 4}

アルゴリズム

• 与えられた数値を文字列としてエンコードします。さらに、配列をソートした結果も文字列としてエンコードし、これを目標文字列(destination)とします。
• 初期の順列から幅優先探索(BFS)を開始します。各ステップで、現在の順列のプレフィックスを反転することで得られるすべての順列を確認します。
• 未訪問の状態であれば、そこまでの反転回数とともにキューに追加します。
• エンコードされた文字列が目標文字列と一致した時点で、そこまでに必要な反転回数を返します。
• これにより、すべての順列の状態が探索され、その中の最小反転回数が答えとして返されます。

実装例

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int minimumPrefixReversals(int *a, int n) {
    string start = "";
    string destination = "", t, r;
    for (int i = 0; i < n; i++) {
        start += to_string(a[i]);
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        destination += to_string(a[i]);
    }
    queue<pair<string, int> > qu;
    pair<string, int> p;
    qu.push(make_pair(start, 0));
    if (start == destination) {
        return 0;
    }
    while (!qu.empty()) {
        p = qu.front();
        t = p.first;
        qu.pop();
        for (int j = 2; j <= n; j++) {
            r = t;
            reverse(r.begin(), r.begin() + j);
            if (r == destination) {
                return p.second + 1;
            }
            qu.push(make_pair(r, p.second + 1));
        }
    }
}
int main() {
    int a[] = { 1, 2, 4, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Minimum reversal: " << minimumPrefixReversals(a, n) << endl;
    return 0;
}

出力

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

Minimum reversal: 3

補足

実用上は、同一の順列を重複して探索しないよう、訪問済みの状態を set<string> などで管理することで、探索効率を大幅に改善できます。BFSは各状態を最短距離で訪問するため、最初に目標文字列へ到達した時点の反転回数が必ず最小値となります。