अवधारणा
दिए गए लंबाई m के स्ट्रिंग के संबंध में जिसमें केवल लोअरकेस अल्फाबेट हैं, हमारा कार्य स्ट्रिंग का nवां क्रमपरिवर्तन लेक्सिकोग्राफिक रूप से निर्धारित करना है।
इनपुट
str[] = "pqr", n = 3
आउटपुट
परिणाम = "qpr"
व्याख्या
क्रमबद्ध क्रम में सभी संभावित क्रमपरिवर्तन - pqr, prq, qpr, qrp, rpq, rqp
इनपुट
str[] = "xyx", n = 2
आउटपुट
परिणाम = "xyx"
व्याख्या
क्रमबद्ध क्रम में सभी संभावित क्रमपरिवर्तन - xxy, xyx, yxx
विधि
यहां हम इस समस्या को हल करने के लिए कुछ गणितीय अवधारणा का उपयोग करते हैं।
अवधारणा निम्नलिखित तथ्यों पर आधारित है।
यहां, N वर्णों (सभी विशिष्ट) द्वारा उत्पन्न स्ट्रिंग के क्रमपरिवर्तन की कुल संख्या N! है
अब, N वर्णों द्वारा उत्पन्न स्ट्रिंग के क्रमपरिवर्तन की कुल संख्या (इस मामले में वर्ण C1 की आवृत्ति M1 है, C2 की M2… और इसी तरह वर्ण Ck की आवृत्ति Mk है) N!/(M1! * M2! *… .Mk!) है।
फिर, N वर्णों (सभी विशिष्ट) द्वारा उत्पन्न स्ट्रिंग के क्रमपरिवर्तन की कुल संख्या एक विशेष वर्ण को ठीक करने के बाद
समाधान तक पहुंचने के लिए नीचे दिए गए चरणों का पालन किया जा सकता है।
सबसे पहले, हम एक सरणी freq[] में सभी वर्णों की आवृत्तियों की गणना करते हैं।
वर्तमान में स्ट्रिंग में मौजूद पहले सबसे छोटे वर्ण से (सबसे छोटा सूचकांक i जैसे कि
freq[i] > 0), हम उस विशेष i-वें वर्ण को पहले वर्ण के रूप में मानने के बाद संभव अधिकतम क्रमपरिवर्तनों की संख्या की गणना करते हैं।
यह देखा गया है कि यदि यह योग मान दिए गए n से अधिक है, तो हम उस वर्ण को पहला परिणाम आउटपुट वर्ण के रूप में सेट करते हैं, freq[i] घटाते हैं, और शेष n-1 वर्णों के लिए समान जारी रखते हैं।
यह देखा गया है कि, दूसरी ओर, यदि गिनती आवश्यक n से छोटी है, तो आवृत्ति तालिका में अगले वर्ण के लिए पुनरावृति करें और बार-बार गिनती को संशोधित करें जब तक कि हमें एक वर्ण नहीं मिल जाता जो आवश्यक n से अधिक गिनती उत्पन्न करता है।
यह ध्यान दिया जाना चाहिए कि उपरोक्त विधि की समय जटिलता O(n) होगी यानी स्ट्रिंग लंबाई के क्रम की।
उदाहरण
// nवां क्रमपरिवर्तन प्रिंट करने के लिए C++ प्रोग्राम #include <bits/stdc++.h> using namespace std; #define ll long long int const int MAX_CHAR1 = 26; const int MAX_FACT1 = 20; ll fact1[MAX_FACT1]; // फ़ैक्टोरियल की गणना के लिए उपयोगिता दिखाता है void precomputeFactorials(){ fact1[0] = 1; for (int i = 1; i < MAX_FACT1; i++) fact1[i] = fact1[i - 1] * i; } // nवें क्रमपरिवर्तन के लिए फ़ंक्शन दिखाता है void nPermute(char str1[], int n1){ precomputeFactorials(); // दिए गए स्ट्रिंग की लंबाई दर्शाता है int len1 = strlen(str1); // सभी वर्णों की आवृत्तियों को गिनने के लिए उपयोग किया जाता है int freq1[MAX_CHAR1] = { 0 }; for (int i = 0; i < len1; i++) freq1[str1[i] - 'a']++; // आउटपुट स्ट्रिंग के लिए out1 स्ट्रिंग दिखाता है char out1[MAX_CHAR1]; // योग n1 के बराबर होने तक पुनरावृति करने के लिए उपयोग किया जाता है int sum1 = 0; int k1 = 0; // हम इस लूप में n1 और sum1 दोनों को संशोधित करते हैं। while (sum1 != n1) { sum1 = 0; // freq1[] में मौजूद वर्णों की जांच करें for (int i = 0; i < MAX_CHAR1; i++) { if (freq1[i] == 0) continue; // वर्ण हटाएं freq1[i]--; // एक विशेष वर्ण को ठीक करने के बाद sum1 की गणना करें int xsum1 = fact1[len1 - 1 - k1]; for (int j = 0; j < MAX_CHAR1; j++) xsum1 /= fact1[freq1[j]]; sum1 += xsum1; // अब यदि sum1 > n1 तो उस वर्ण को वर्तमान वर्ण के रूप में ठीक करें // और sum1 और आवश्यक nth को संशोधित करें // उस स्थिति पर वर्ण को ठीक करने के बाद if (sum1 >= n1) { out1[k1++] = i + 'a'; n1 -= (sum1 - xsum1); break; } // अब यदि sum1 < n1, तो वर्ण को वापस जोड़ें if (sum1 < n1) freq1[i]++; } } // अब यदि sum1 == n1 का अर्थ है यह // वर्ण अपना // महत्तम क्रमपरिवर्तन प्रदान करेगा // nth क्रमपरिवर्तन के रूप में for (int i = MAX_CHAR1 - 1; k1 < len1 && i >= 0; i--) if (freq1[i]) { out1[k1++] = i + 'a'; freq1[i++]--; } // स्ट्रिंग समाप्ति वर्ण जोड़ने और परिणाम प्रिंट करने के लिए उपयोग किया जाता है out1[k1] = '\0'; cout << out1; } // ड्राइवर प्रोग्राम int main(){ int n1 = 5; char str1[] = "tutorialspoint"; // int n1 = 3; // char str1[] = "pqr"; //int n1 = 2; //char str1[] = "xyx"; nPermute(str1, n1); return 0; }
आउटपुट
aiilnooprtsttu
