একটি অ্যারেতে, একটি জোড়া a[i], a[j] একটি বিপরীত হিসাবে পরিচিত হয় যদি a[i]> a[j] এবং i
আমরা ব্রুট ফোর্স অ্যাপ্রোচ প্রয়োগ করতে পারি , যা প্রথমে প্রথম N সংখ্যার সমস্ত স্থানান্তর খুঁজে বের করছে এবং তারপরে K-এর সমান কিনা তা সমস্ত বিপরীত চেক করছে। যদি হ্যাঁ, তাহলে ফলাফল কাউন্টার বৃদ্ধি করা।
এই পদ্ধতিতে, আমাদের কাছে প্রথম N প্রাকৃতিক সংখ্যাগুলির N সংখ্যা রয়েছে। সেই সংখ্যার সমস্ত স্থানান্তরগুলি অন্য কোথাও গণনা করা হয় যেখান থেকে আমরা K পারমিউটেশনগুলি খুঁজছি। এটি খুঁজে বের করার জন্য, আমরা সমস্ত পারমুটেশনে পরবর্তী সংখ্যা Nth(সবচেয়ে বড়) সন্নিবেশ করব এবং সেই সংখ্যাগুলি খুঁজব যার বিপরীত সংখ্যা K-এর সমান এই সংখ্যাটি যোগ করার পরে আমাদের ফলাফলে গণনা করা উচিত। (N – 1) সংখ্যার এই ধরনের পারমুটেশন গ্রহণ করে যার (K – 3) ইনভার্সন নেই, আমরা নতুন সংখ্যাটি শেষ থেকে 3য় সূচকে স্থানান্তর করব। বিপরীত সংখ্যা হবে K, এবং find_permutations(N-1, K-3) হবে আমাদের উত্তর। একই যুক্তি অন্যান্য ইনভার্সেশনের জন্য ব্যবহার করা যেতে পারে, এবং আমরা চূড়ান্ত উত্তর হিসাবে উপরের পুনরাবৃত্তিতে পৌঁছাব।
ইনপুট − N =4, K =3
আউটপুট − 6
এই নিবন্ধে, আমরা O(n * k) থেকে K ইনভার্সেশনের সাথে ক্রমিউটেশনের সংখ্যা খুঁজে পেতে একটি সমস্যার সমাধান করি। সময় জটিলতা। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি ( স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আশা করি আপনি এই নিবন্ধটি সহায়ক বলে মনে করেন৷Input: N = 4, K = 1
Output: 3
Explanation: Permutation of the first N numbers in total : 1234, 1243, 1324 and 2134. With 1 inversion we have 1243, 1324 and 2134.
Input : N = 3, K = 2
Output : 3
Explanation: Permutation of the first N numbers in total : 123, 132, 213, 231, 312, and 321 with 2 inversions we have 231, 312 and 321.
সমাধান খোঁজার পদ্ধতি
দক্ষ পদ্ধতি
ইনপুট
#include <bits/stdc++.h>
using namespace std;
const int X = 100;
int a = 0;
int arr[X][X];
// recursive function
int find_permutations (int N_numbers, int K_inversion){
if (N_numbers == 0){
return 0; // return 0 when N becomes 0
}
if (K_inversion == 0)
return 1; // return 1 when K becomes 1
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; // taking input from user
cin >> K;
cout << find_permutations (N, K);
return 0;
} আউটপুট
0
উপসংহার
