एक सरणी में, एक जोड़ी a[i], a[j] को इनवर्जन के रूप में जाना जाता है यदि a[i] > a[j] और i < j। हमारे पास दो संख्याएं N और k हैं, और यह पता लगाने की आवश्यकता है कि पहले N संख्याओं के कितने संभावित क्रमचय पूर्ण K इनवर्जन में समाप्त होते हैं। तो यहाँ उदाहरण है:
Input: N = 4, K = 1 Output: 3 Explanation: पहले N संख्याओं के कुल क्रमचय: 1234, 1243, 1324 और 2134। 1 इनवर्जन के साथ हमारे पास 1243, 1324 और 2134 हैं। Input : N = 3, K = 2 Output : 3 Explanation: पहले N संख्याओं के कुल क्रमचय: 123, 132, 213, 231, 312, और 321 जिनमें 2 इनवर्जन हैं वे 231, 312 और 321 हैं।
समाधान खोजने का दृष्टिकोण
हम ब्रूट फोर्स दृष्टिकोण लागू कर सकते हैं, जो पहले N संख्याओं के सभी क्रमचय ढूंढना है और फिर सभी इनवर्जन की जांच करना है कि क्या यह K के बराबर है या नहीं। यदि हाँ, तो परिणाम काउंटर को बढ़ाना।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हमारे पास पहले 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 0 हो जाए तो 0 लौटाएं } if (K_inversion == 0) return 1; // जब K 1 हो जाए तो 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; } // मुख्य फ़ंक्शन 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 और अन्य भाषाओं में लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।
