এই প্রোগ্রামিং সমস্যায়, আমাদের একটি স্ট্রিং দেওয়া হয়েছে এবং আমাদেরকে স্ট্রিং উপাদানগুলির স্বতন্ত্র সাজানো পারমুটেশনগুলি প্রিন্ট করতে হবে যা গঠিত হতে পারে। এই সমস্যাটির শর্ত হল যে স্ট্রিংটিতে এমন একটি অক্ষর থাকতে পারে যা একাধিকবার উঠবে। এছাড়াও, প্রদত্ত স্ট্রিংটি সাজানো ক্রমে ইনপুট করা হয়।
ধারণাটি আরও ভালভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
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
যুক্তি −
এই স্ট্রিং থেকে মোট ৩টি! =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
