在C ++中以排序(字典顺序)打印所有排列
在这个问题中,我们给了一个长度为n的字符串,并且必须按排序顺序打印字符串的所有字符排列。
让我们以一个例子来理解这个问题:
输入: “ 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
以上是 在C ++中以排序(字典顺序)打印所有排列 的全部内容, 来源链接: utcz.com/z/334766.html