การเรียงสับเปลี่ยนที่แต่ละสมาชิกบอกจำนวนสมาชิกก่อนหรือหลังมัน

ในส่วนนี้เราจะดูปัญหา: มี n สมาชิกในอาร์เรย์ ต้องตรวจสอบว่ามี permutation ของอาร์เรย์นั้นที่ทำให้แต่ละสมาชิกบอกจำนวนสมาชิกที่อยู่ก่อนหรือหลังมันได้หรือไม่

ตัวอย่าง: อาร์เรย์ = {2, 1, 3, 3} Permutation ที่ถูกต้องคือ {3, 1, 2, 3} 3 ตัวแรกบอกว่ามี 3 ตัวหลังมัน 1 บอกว่ามี 1 ตัวก่อนมัน 2 บอกว่ามี 2 ตัวก่อนมัน 3 ตัวสุดท้ายบอกว่ามี 3 ตัวก่อนมัน

อัลกอริทึม

checkPermutation(arr, n)

begin
    define a hashmap to hold frequencies (key and value are integers)
    for each element e in arr, do
        increase map[e] by 1
    done
    for i := 0 to n-1, do
        if map[i] is non-zero, then
            decrease map[i] by 1
        else if map[n-i-1] is non-zero, then
            decrease map[n-i-1] by 1
        else
            return false
        end if
    done
    return true
end

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <map>
using namespace std;

bool checkPermutation(int arr[], int n) {
    map 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;
}

int 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