各要素が前後の要素の数を示す順列は存在するか？判定アルゴリズムとC++実装

本記事では、順列に関する興味深いアルゴリズム問題を取り上げます。長さ n の配列が与えられたとき、「各要素の値が、その要素より前にある要素の個数、または後ろにある要素の個数のいずれかと一致する」ような順列が存在するかどうかを判定します。

例として、配列が {2, 1, 3, 3} の場合を考えてみましょう。条件を満たす順列の一つは {3, 1, 2, 3} です。

• 先頭の 3 … 自分より後ろに3つの要素があることを示しています。
• 2番目の 1 … 自分より前に1つの要素があることを示しています。
• 3番目の 2 … 自分より前に2つの要素があることを示しています。
• 最後の 3 … 自分より前に3つの要素があることを示しています。

このように、すべての要素が「前方の要素数」か「後方の要素数」のどちらか一方に一致していれば、答えは「存在する（true）」となります。

アルゴリズムの考え方

この問題は、ハッシュマップ（連想配列）で出現頻度を管理することで効率的に解けます。手順のポイントは次の通りです。

1. まず、配列中の各値の出現回数をハッシュマップに記録します。
2. 位置 i（0 ～ n-1）にある要素は、「前に i 個の要素がある」か「後に n-i-1 個の要素がある」ことになります。
3. したがって、値 i がまだ残っていればそれを消費し、なければ値 n-i-1 を消費します。どちらも残っていない場合は、条件を満たす順列が存在しないため false を返します。
4. すべての位置で処理できれば true を返します。

擬似コード： checkPermutation(arr, n)

begin
    キー・値ともに整数型のハッシュマップを定義し、頻度を管理する
    arr 内の各要素 e について:
        map[e] を 1 増やす
    for i := 0 to n-1:
        if map[i] が非ゼロなら:
            map[i] を 1 減らす      // 「前に i 個ある」要素として使用
        else if map[n-i-1] が非ゼロなら:
            map[n-i-1] を 1 減らす  // 「後に n-i-1 個ある」要素として使用
        else:
            return false
    return true
end

計算量は、std::map を用いた場合、時間 O(n log n)（unordered_map を使えば平均 O(n)）、空間 O(n) となります。

C++ による実装例

#include<iostream>
#include<map>
using namespace std;
bool checkPermutation(int arr[], int n) {
    map<int, int> freq_map;
    for(int i = 0; i < n; i++){ // 各数値の出現回数を記録
        freq_map[arr[i]]++;
    }
    for(int i = 0; i < n; i++){
        if(freq_map[i]){ // 「現在位置より前の要素数」として使用できるか
            freq_map[i]--;
        } else if(freq_map[n-i-1]){ // 「後ろの要素数」として使用できるか
            freq_map[n-i-1]--;
        } else {
            return false;
        }
    }
    return true;
}
main() {
    int data[] = {3, 2, 3, 1};
    int n = sizeof(data)/sizeof(data[0]);
    if(checkPermutation(data, n)){
        cout << "Permutation is present";
    } else {
        cout << "Permutation is not present";
    }
}

出力結果

Permutation is present

入力配列 {3, 2, 3, 1} は、例えば {3, 1, 2, 3} のように並べ替えることで条件を満たせるため、「Permutation is present（順列が存在する）」と出力されます。逆に、どのような並べ替えでも条件を満たせない場合は「Permutation is not present」と表示されます。