|
| 1 | +#include<stdio.h> |
| 2 | +#include<string.h> |
| 3 | +#include<stdlib.h> |
| 4 | + |
| 5 | +voidswap(char*left,char*right){ |
| 6 | +chartemp=*left; |
| 7 | +*left=*right; |
| 8 | +*right=temp; |
| 9 | +} |
| 10 | + |
| 11 | +intcompare (constvoid*a,constvoid*b){ |
| 12 | +return (*(char*)a-*(char*)b ); |
| 13 | +} |
| 14 | + |
| 15 | +voidPrintSortedPermutations(charstr[]) |
| 16 | +{ |
| 17 | +intstrSize=strlen(str); |
| 18 | +qsort(str,strSize,sizeof(char),compare); |
| 19 | + |
| 20 | +intlargerPermFound=1; |
| 21 | +do{ |
| 22 | +// 1. Print permutation |
| 23 | +printf("%s\n",str); |
| 24 | +// 2. Find rightmost char that is smaller than char to its right |
| 25 | +inti; |
| 26 | +for (i=strSize-2;i >=0&&str[i] >=str[i+1];--i){} |
| 27 | + |
| 28 | +// if we couldn't find one, we're finished, else we can swap |
| 29 | +if (i >=0){ |
| 30 | +// 3. find character at index j such that str[j] = min(str[k]) && str[k] > str[i] for all k > i |
| 31 | +intj=i+1,k; |
| 32 | +for(k=j;k<strSize&&str[k];k++){ |
| 33 | +if (str[k]>str[i]&&str[k]<str[j]) |
| 34 | +j=k; |
| 35 | + } |
| 36 | +// 3. Swap chars at i and j |
| 37 | +swap(&str[i],&str[j]); |
| 38 | +// 4. Sort string to the right of i |
| 39 | +qsort(str+i+1,strSize-i-1,sizeof(char),compare); |
| 40 | + } |
| 41 | +elselargerPermFound=0; |
| 42 | + } |
| 43 | +while(largerPermFound); |
| 44 | +} |
| 45 | + |
| 46 | +intmain() { |
| 47 | +intn;//size of string |
| 48 | +scanf("%d\n",&n); |
| 49 | +charstr[n]; |
| 50 | +scanf("%s",str); |
| 51 | +PrintSortedPermutations(str); |
| 52 | +return0; |
| 53 | +} |