इस प्रोग्रामिंग समस्या में, हमें एक स्ट्रिंग दी गई है और हमें स्ट्रिंग तत्वों से बनने वाले विशिष्ट सॉर्टेड क्रमपरिवर्तन प्रिंट करने हैं। इस समस्या की शर्त यह है कि स्ट्रिंग में एक वर्ण हो सकता है जो एक से अधिक बार आएगा। साथ ही, दी गई स्ट्रिंग सॉर्ट क्रम में इनपुट की गई है।
आइए एक उदाहरण लेकर अवधारणा को बेहतर ढंग से समझते हैं,
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.
क्रमपरिवर्तन एक सेट के सभी तत्वों को एक विशिष्ट क्रम या प्रकार के आधार पर पुनर्व्यवस्थित करना है। सेट क्रमबद्ध हो सकता है या नहीं भी।
अब चूंकि हमने समस्या के बारे में सब कुछ सीख लिया है। आइए इस समस्या को हल करने के लिए एक तर्क बनाने का प्रयास करते हैं,
हम क्रमपरिवर्तन से संबंधित कुछ गणितीय सूत्र जानते हैं। एक स्ट्रिंग द्वारा उत्पन्न कुल स्ट्रिंग्स की संख्या जिसमें n वर्ण हैं और सभी अलग हैं, n! द्वारा दी जाती है। यदि स्ट्रिंग में वर्ण हैं जो स्वयं को दोहरा रहे हैं तो, स्ट्रिंग्स की संख्या n! / i! द्वारा दी जाती है।
स्ट्रिंग STURS के लिए, उत्पन्न होने वाली कुल स्ट्रिंग्स की संख्या 5! / 2! = 60 है। चूंकि s स्ट्रिंग में 2 बार आता है।
इसका उपयोग करके हम बनने वाली स्ट्रिंग्स की संख्या जानते हैं। अब, हमें उन स्ट्रिंग्स को बनाना है। इसके लिए पहले हम स्ट्रिंग को सॉर्ट करेंगे यदि नहीं (स्ट्रिंग इनपुट सॉर्टेड होगी) ताकि अंतिम स्ट्रिंग सॉर्टेड रूप में हो। अब, स्ट्रिंग के पहले वर्ण को फिक्स करें और बाकी सभी के क्रमपरिवर्तन ढूंढें और इसी तरह। यह सभी आवश्यक क्रमपरिवर्तनों को सॉर्टेड तरीके से देगा।
उदाहरण के लिए,
इनपुट - RST
तर्क -
इस स्ट्रिंग से कुल 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
