इस समस्या में, हमें n वर्णों की एक स्ट्रिंग दी गई है और हमें स्ट्रिंग के वर्णों के सभी क्रमपरिवर्तन प्रिंट करने हैं। स्ट्रिंग के वर्णों को दोहराने की अनुमति है। क्रमपरिवर्तन की प्रिंटिंग वर्णमाला क्रम में (लेक्सिकोग्राफिकली क्रमबद्ध क्रम) में की जानी चाहिए।
विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं :
इनपुट - XY
आउटपुट - XX, XY, YX, YY
इस समस्या को हल करने के लिए, हमें फिक्स और रिकर तर्क का उपयोग करने की आवश्यकता है। यहां, हम सरणी के पहले इंडेक्स पर एक तत्व को फिक्स करेंगे और फिर अनुक्रम में अगले तत्वों के लिए रिकर्सिव कॉल करेंगे।
आइए एक कार्यान्वयन उदाहरण देखें जो समाधान को आपके लिए स्पष्ट कर देगा।
इनपुट स्ट्रिंग XY।
पहले तत्व को 1 इंडेक्स पर फिक्स करें: X_
अन्य तत्वों को रिकर्सिवली कॉल करें और भरें: XX -> XY
अब अगले तत्व को इंडेक्स 1 पर फिक्स करें: Y_
अन्य तत्वों को रिकर्सिवली कॉल करें और भरें: YX -> YY
यही तर्क 3,4,n लंबाई की स्ट्रिंग के लिए इस्तेमाल किया जा सकता है।
उदाहरण
#include <iostream> #include<string.h> using namespace std; void printPermutations(char *str, char* permutations, int last, int index){ int i, len = strlen(str); for ( i = 0; i < len; i++ ) { permutations[index] = str[i] ; if (index == last) cout<<permutations <<"\t"; else printPermutations (str, permutations, last, index+1); } } int main() { char str[] = "ABC"; cout<<"All permutations of the string with repetition of "<<str<<" are: "<<endl ; int len = strlen(str) ; char permutations[len]; printPermutations (str, permutations, len-1, 0); return 0; } आउटपुट
All permutations of the string with repetition of ABC are: AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC
