এই সমস্যায়, আমাদের দৈর্ঘ্যের একটি স্ট্রিং দেওয়া হয়েছে এবং আমাদের স্ট্রিংটির অক্ষরগুলির সমস্ত পারমুটেশনগুলি সাজানো ক্রমে প্রিন্ট করতে হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক :
ইনপুট: 'XYZ'
আউটপুট: XYZ, XZY, YXZ, YZX, ZXY, ZYX৷
৷এখানে আমাদেরকে লেক্সিকোগ্রাফিকাল ক্রমানুসারে (বর্ণানুক্রমিকভাবে ক্রমবর্ধমান ক্রম) সমস্ত স্থানান্তর মুদ্রণ করতে হবে।
এই সমস্যাটি সমাধান করার জন্য, আমাদের প্রথমে অ্যারেটিকে বর্ণানুক্রমিকভাবে ক্রমবর্ধমান ক্রমে সাজাতে হবে, সাজানো অ্যারেটি হল পারমুটেশনের প্রথম উপাদান। এবং তারপর স্ট্রিং এর পরবর্তী উচ্চ ক্রম স্থানান্তর তৈরি করুন।
নীচের কোডটি আপনার কাছে সমাধানটিকে আরও স্পষ্ট করে তুলবে :
উদাহরণ
#include<iostream>
#include<string.h>
using namespace std;
int compare(const void *a, const void * b){
return ( *(char *)a - *(char *)b );
}
void swap(char* a, char* b) {
char t = *a;
*a = *b;
*b = t;
}
int finduBound(char str[], char first, int l, int h) {
int ubound = l;
for (int i = l+1; i <= h; i++)
if (str[i] > first && str[i] < str[ubound])
ubound = i;
return ubound;
}
void generatePermutaion ( char str[] ) {
int size = strlen(str);
qsort( str, size, sizeof( str[0] ), compare );
bool isFinished = false;
while ( ! isFinished ) {
cout<<str<<"\t";
int i;
for ( i = size - 2; i >= 0; --i )
if (str[i] < str[i+1])
break;
if ( i == -1 )
isFinished = true;
else {
int ubound = finduBound( str, str[i], i + 1, size - 1 );
swap( &str[i], &str[ubound] );
qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );
}
}
}
int main() {
char str[] = "NOPQ";
cout<<"Permutation in Sorted order :\n";
generatePermutaion(str);
return 0;
} আউটপুট
Permutation in Sorted order : NOPQ NOQP NPOQ NPQO NQOP NQPO ONPQ ONQP OPNQ OPQN OQNP OQPN PNOQ PNQO PONQ POQN PQNO PQON QNOP QNPO QONP QOPN QPNO QPON
