इस समस्या में, हमें लंबाई n की एक स्ट्रिंग दी जाती है और हमें स्ट्रिंग के वर्णों के सभी क्रमपरिवर्तनों को क्रमबद्ध क्रम में प्रिंट करना होता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं:
इनपुट: 'एक्सवाईजेड'
आउटपुट: 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