একটি পারমুটেশন যেখানে প্রতিটি এলিমেন্ট তার আগে বা পরে থাকা এলিমেন্টের সংখ্যা নির্দেশ করে

এই অনুচ্ছেদে আমরা একটি সমস্যা দেখব। এখানে n এলিমেন্ট একটি অ্যারেতে দেওয়া আছে। আমাদের চেক করতে হবে এমন একটি পারমুটেশন আছে কিনা, যাতে প্রতিটি এলিমেন্ট তার আগে বা পরে থাকা এলিমেন্টের সংখ্যা নির্দেশ করে।

ধরা যাক অ্যারে এলিমেন্টগুলো হলো {২, ১, ৩, ৩}। উপযুক্ত পারমুটেশন হলো {৩, ১, ২, ৩}। এখানে প্রথম ৩ নির্দেশ করছে এর পরে ৩টি এলিমেন্ট আছে, ১ নির্দেশ করছে এর আগে ১টি এলিমেন্ট আছে। ২ নির্দেশ করছে এর আগে ২টি এলিমেন্ট আছে এবং শেষ ৩ নির্দেশ করছে এর আগে ৩টি এলিমেন্ট আছে।

অ্যালগরিদম

checkPermutation(arr, n)

begin define a hashmap to hold frequencies. The key and value are of integer type of the map. 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

উদাহরণ

#include #include using namespace std; bool checkPermutation(int arr[], int n) { map freq_map; for(int i = 0; i < n; i++){ //get the frequency of each number freq_map[arr[i]]++; } for(int i = 0; i < n; i++){ if(freq_map[i]){ //count number of elements before current element freq_map[i]--; } else if(freq_map[n-i-1]){ //count number of elements after current element 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