একটি অ্যারেতে একটি পেয়ার a[i], a[j] ইনভার্সন বলা হয় যদি a[i] > a[j] এবং i < j। আমাদের কাছে দুটি সংখ্যা N এবং k আছে, এবং আমাদের বের করতে হবে প্রথম N সংখ্যার কতগুলো সম্ভাব্য পারমুটেশন আছে যারা ঠিক K ইনভার্সন দিয়ে শেষ হয়। উদাহরণ:
ইনপুট: N = 4, K = 1 আউটপুট: 3 ব্যাখ্যা: প্রথম N সংখ্যার সব পারমুটেশন: 1234, 1243, 1324 এবং 2134। 1 ইনভার্সনসহ পারমুটেশন: 1243, 1324 এবং 2134। ইনপুট : N = 3, K = 2 আউটপুট : 3 ব্যাখ্যা: প্রথম N সংখ্যার সব পারমুটেশন: 123, 132, 213, 231, 312, এবং 321 2 ইনভার্সনসহ: 231, 312 এবং 321।
সমাধানের পদ্ধতি
আমরা ব্রুট ফোর্স পদ্ধতি próp করতে পারি, যা হলো প্রথম N সংখ্যার সকল পারমুটেশন বের করে তারপর সকল ইনভার্সন চেক করা যে সেটি K-এর সমান কিনা। হ্যাঁ হলে রেজাল্ট কাউন্টার বাড়ানো।
দক্ষ পদ্ধতি (Efficient Approach)
এই পদ্ধতিতে, আমাদের কাছে প্রথম N প্রাকৃতিক সংখ্যার N ডিজিট আছে। সকল পারমুটেশন কোথাও অন্যत्र হিসাব করা হয়েছে যেখান থেকে আমরা K পারমুটেশন খুঁজছি। সেটি বের করতে, আমরা পরবর্তী Nth (সর্বোচ্চ) সংখ্যাটি সকল পারমুটেশনে ইনসার্ট করব এবং যেসব সংখ্যার ইনভার্সন কাউন্ট এই সংখ্যা যোগ করার পর K-এর সমান হয় সেগুলো আমাদের রেজাল্টে কাউন্ট হবে। (N-1) সংখ্যার ওই পারমুটেশন নিব যাদের (K-3) ইনভার্সন নেই, নতুন সংখ্যাটি শেষ থেকে ৩য় ইনডেক্সে শিফট করব। ইনভার্সন সংখ্যা হবে K, এবং find_permutations(N-1, K-3) হবে আমাদের উত্তর। একই লজিক অন্যান্য ইনভার্সনের জন্যও ব্যবহার করা যায়, এবং আমরা উপরের রিকার্সন ফর্মুলায় পৌঁছাব।
ইনপুট
#include <bits/stdc++.h> using namespace std; const int X = 100; int a = 0; int arr[X][X]; // রিকার্সিভ ফাংশন int find_permutations (int N_numbers, int K_inversion){ if (N_numbers == 0){ return 0; // N ০ হলে ০ রিটার্ন } if (K_inversion == 0) return 1; // K ১ হলে ১ রিটার্ন if (arr[N_numbers][K_inversion] != 0) return arr[N_numbers][K_inversion]; int result = 0; for (int i = 0; i <= K_inversion; i++){ if (i <= N_numbers - 1) result += find_permutations (N_numbers - 1, K_inversion - i); } arr[N_numbers][K_inversion] = result; return result; } // main function int main (){ int N, K; cin >> N; // ইউজার থেকে ইনপুট cin >> K; cout << find_permutations (N, K); return 0; }
আউটপুট
0
ইনপুট − N = 4, K = 3
আউটপুট − 6
উপসংহার
এই আর্টিকেলে আমরা O(N * K) সময় জটিলতায় K ইনভার্সন সহ পারমুটেশন সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সমাধানের পূর্ণ পদ্ধতি (সাধারণ এবং দক্ষ) শিখেছি। একই প্রোগ্রাম C, Java, Python বা অন্য ভাষায় লেখা যায়। আশা করি এই আর্টিকেলটি সহায়ক হবে।
