एक सरणी में, एक जोड़ी a[i], a[j] को व्युत्क्रम के रूप में जाना जाता है यदि a[i]> a[j] और i
हम क्रूर बल दृष्टिकोण . लागू कर सकते हैं , जो पहले पहले N नंबरों के सभी क्रमपरिवर्तन ढूंढ रहा है और फिर सभी व्युत्क्रमों की जाँच कर रहा है कि यह K के बराबर है या नहीं। यदि हाँ, तो परिणामी काउंटर को बढ़ाएँ।
इस दृष्टिकोण में, हमारे पास पहले एन प्राकृतिक संख्याओं के एन अंक हैं। उस संख्या के सभी क्रमपरिवर्तन की गणना कहीं और की जाती है, जहाँ से हम K क्रमपरिवर्तन की तलाश कर रहे हैं। इसे खोजने के लिए, हम सभी क्रमपरिवर्तनों में अगला नंबर Nth (सबसे बड़ा) डालेंगे और उन नंबरों की तलाश करेंगे जिनकी व्युत्क्रम संख्या K के बराबर है, इस संख्या को जोड़ने के बाद हमारे परिणाम में गिना जाना चाहिए। (एन -1) संख्याओं के ऐसे क्रमपरिवर्तन लेते हुए जिनमें (के - 3) उलटा नहीं है, हम नई संख्या को अंतिम से तीसरे सूचकांक पर स्थानांतरित कर देंगे। व्युत्क्रमों की संख्या K होगी, और find_permutations(N-1, K-3) हमारा उत्तर होगा। अन्य व्युत्क्रमों के लिए समान तर्क का उपयोग किया जा सकता है, और हम अंतिम उत्तर के रूप में उपरोक्त पुनरावृत्ति पर पहुंचेंगे।
इनपुट - एन =4, के =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
निष्कर्ष
