इस प्रोग्रामिंग समस्या में, हमें एक स्ट्रिंग दी जाती है और हमें स्ट्रिंग तत्वों के अलग-अलग क्रमबद्ध क्रमपरिवर्तन मुद्रित करने होते हैं जिन्हें बनाया जा सकता है। इस समस्या के साथ शर्त यह है कि स्ट्रिंग में एक वर्ण हो सकता है जो एक से अधिक बार उत्पन्न होगा। साथ ही, दिए गए स्ट्रिंग को क्रमबद्ध क्रम में इनपुट किया जाता है।
आइए अवधारणा को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं,
Input : ABD Output : ABD , ADB , BAD , BDA , DAB , DBA INPUT : RSTU OUTPUT : RSTU , RSUT , RTSU , RTUS , RUST , RUTS , SRTU , SRUT , STRU , STUR , SURT , SUTR , TRSU , TRUS , TSRU , TSUR , TURS , TUSR , URST , URTS , USRT , USTR , UTRS , UTSR.
PERMUTATION एक विशिष्ट अनुक्रम या प्रकार के आधार पर एक सेट के सभी तत्वों को पुनर्व्यवस्थित कर रहा है। सेट का आदेश दिया जा सकता है या आदेश नहीं दिया जा सकता है।
अब जैसा कि हमने समस्या के बारे में सब कुछ जान लिया है। आइए समस्या को हल करने के लिए एक तर्क बनाने की कोशिश करें,
हम क्रमपरिवर्तन से संबंधित कुछ गणितीय सूत्र जानते हैं। स्ट्रिंग्स की कुल संख्या जो एक स्ट्रिंग द्वारा उत्पन्न होती है जिसमें n वर्ण होते हैं और सभी अलग-अलग होते हैं, n! द्वारा दिया जाता है। यदि स्ट्रिंग में ऐसे वर्ण हैं जो स्वयं को दोहरा रहे हैं, तो स्ट्रिंग्स की संख्या n! / मैं! ।
स्ट्रिंग STURS के लिए, उत्पन्न होने वाली स्ट्रिंग की कुल संख्या 5 है! / 2! =60. चूँकि s स्ट्रिंग में 2 बार आता है।
इसका उपयोग करके हम बनाए गए स्ट्रिंग की संख्या जानते हैं। अब, हमें उन स्ट्रिंग्स को बनाना है। इसके लिए पहले हम स्ट्रिंग को सॉर्ट करेंगे यदि नहीं (स्ट्रिंग इनपुट को सॉर्ट किया जाएगा) ताकि अंतिम स्ट्रिंग सॉर्ट किए गए रूप में हो। अब, स्ट्रिंग के पहले अक्षर को ठीक करें और बाकी सभी का क्रमचय ज्ञात करें और इसी तरह। यह सभी आवश्यक क्रमपरिवर्तन एक क्रमबद्ध तरीके से देगा।
उदाहरण के लिए,
इनपुट - आरएसटी
>तर्क -
इस स्ट्रिंग से कुल 3! =6 क्रमपरिवर्तन बनाए जा सकते हैं।
आइए R को ठीक करें और s और t से क्रमपरिवर्तन खोजें। यह 2 तार देगा RST, RTS.
इसी तरह S को ठीक करने से SRT, STR. मिलेगा और T को ठीक करने से TRS, TSR. मिलेगा
तो, यह आउटपुट देगा - RST, RTS, SRT, STR, TRS, TSR। जो क्रम में हैं।
अब, इस समस्या को हल करने के लिए एक प्रोग्राम बनाते हैं,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
bool swaper(char str[], int start, int curr){
for (int i = start; i < curr; i++)
if (str[i] == str[curr])
return 0;
return 1;
}
void printPermutations(char str[], int index, int n){
if (index >= n) {
cout<<str<<"\t";
return;
}
for (int i = index; i < n; i++) {
bool check = swaper(str, index, i);
if (check) {
swap(str[index], str[i]);
printPermutations(str, index + 1, n);
swap(str[index], str[i]);
}
}
}
int main(){
char str[] = "AABC";
int n = strlen(str);
cout<<"The string is : "<<str<<end;
cout<<"The distinct sorted permutations are : \t";
printPermutations(str, 0, n);
return 0;
} आउटपुट
The string is : AABC The distinct sorted permutations are : AABC AACB ABAC ABCA ACBA ACAB BAAC BACA BCAA CABA CAAB CBAA