#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void swap(char* left, char* right)
{
char temp = *left;
*left = *right;
*right = temp;
}
int compare (const void * a, const void * b)
{
return ( *(char*)a - *(char*)b );
}
void PrintSortedPermutations(char* inStr)
{
// Re-implementation of algorithm described here:
// http://w...content-available-to-author-only...s.org/lexicographic-permutations-of-string/
// 0. Ensure input container is sorted
qsort(inStr
, strSize
, sizeof(char), compare
);
int largerPermFound = 1;
do{
// 1. Print next permutation
// 2. Find rightmost char that is smaller than char to its right
int i;
for (i = strSize - 2; i >= 0 && inStr[i] >= inStr[i+1]; --i){}
// if we couldn't find one, we're finished, else we can swap somewhere
if (i > -1)
{
// 3 find character at index j such that
// inStr[j] = min(inStr[k]) && inStr[k] > inStr[i] for all k > i
int j = i+1;
int k;
for(k=j;k<strSize && inStr[k];++k)
{
if (inStr[k] > inStr[i] && inStr[k] < inStr[j])
j = k;
}
// 3. Swap chars at i and j
swap(&inStr[i], &inStr[j]);
// 4. Sort string to the right of i
qsort(inStr
+i
+1, strSize
-i
-1, sizeof(char), compare
); }
else
{
largerPermFound = 0;
}
}while(largerPermFound);
}
int main(void) {
char str[] = "abc";
PrintSortedPermutations(str);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgoKdm9pZCBzd2FwKGNoYXIqIGxlZnQsIGNoYXIqIHJpZ2h0KQp7CgljaGFyIHRlbXAgPSAqbGVmdDsKCSpsZWZ0ID0gKnJpZ2h0OwoJKnJpZ2h0ID0gdGVtcDsKfQppbnQgY29tcGFyZSAoY29uc3Qgdm9pZCAqIGEsIGNvbnN0IHZvaWQgKiBiKQp7CiAgcmV0dXJuICggKihjaGFyKilhIC0gKihjaGFyKiliICk7Cn0Kdm9pZCBQcmludFNvcnRlZFBlcm11dGF0aW9ucyhjaGFyKiBpblN0cikKewoJLy8gUmUtaW1wbGVtZW50YXRpb24gb2YgYWxnb3JpdGhtIGRlc2NyaWJlZCBoZXJlOgoJLy8gaHR0cDovL3cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLnMub3JnL2xleGljb2dyYXBoaWMtcGVybXV0YXRpb25zLW9mLXN0cmluZy8KCWludCBzdHJTaXplID0gc3RybGVuKGluU3RyKTsKCS8vIDAuIEVuc3VyZSBpbnB1dCBjb250YWluZXIgaXMgc29ydGVkCglxc29ydChpblN0ciwgc3RyU2l6ZSwgc2l6ZW9mKGNoYXIpLCBjb21wYXJlKTsKCQoJCglpbnQgbGFyZ2VyUGVybUZvdW5kID0gMTsKCWRvewoJCS8vIDEuIFByaW50IG5leHQgcGVybXV0YXRpb24KCQlwcmludGYoIiVzXG4iLCBpblN0cik7CgkJLy8gMi4gRmluZCByaWdodG1vc3QgY2hhciB0aGF0IGlzIHNtYWxsZXIgdGhhbiBjaGFyIHRvIGl0cyByaWdodAoJCWludCBpOwogICAgICAgIGZvciAoaSA9IHN0clNpemUgLSAyOyBpID49IDAgJiYgaW5TdHJbaV0gPj0gaW5TdHJbaSsxXTsgLS1pKXt9CiAgICAgICAgCiAgICAgICAgLy8gaWYgd2UgY291bGRuJ3QgZmluZCBvbmUsIHdlJ3JlIGZpbmlzaGVkLCBlbHNlIHdlIGNhbiBzd2FwIHNvbWV3aGVyZQogICAgICAgIGlmIChpID4gLTEpCiAgICAgICAgewogICAgICAgIAkvLyAzIGZpbmQgY2hhcmFjdGVyIGF0IGluZGV4IGogc3VjaCB0aGF0IAogICAgICAgIAkvLyBpblN0cltqXSA9IG1pbihpblN0cltrXSkgJiYgaW5TdHJba10gPiBpblN0cltpXSBmb3IgYWxsIGsgPiBpCiAgICAgICAgCWludCBqID0gaSsxOwogICAgICAgIAlpbnQgazsKICAgICAgICAJZm9yKGs9ajtrPHN0clNpemUgJiYgaW5TdHJba107KytrKQogICAgICAgIAl7CiAgICAgICAgCQlpZiAoaW5TdHJba10gPiBpblN0cltpXSAmJiBpblN0cltrXSA8IGluU3RyW2pdKQogICAgCQkJCWogPSBrOwogICAgICAgIAl9CiAgICAgICAgCQogICAgICAgIAkvLyAzLiBTd2FwIGNoYXJzIGF0IGkgYW5kIGoKICAgICAgICAJc3dhcCgmaW5TdHJbaV0sICZpblN0cltqXSk7CiAgICAgICAgCQogICAgICAgIAkvLyA0LiBTb3J0IHN0cmluZyB0byB0aGUgcmlnaHQgb2YgaQogICAgICAgIAlxc29ydChpblN0citpKzEsIHN0clNpemUtaS0xLCBzaXplb2YoY2hhciksIGNvbXBhcmUpOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgIAlsYXJnZXJQZXJtRm91bmQgPSAwOwogICAgICAgIH0KCX13aGlsZShsYXJnZXJQZXJtRm91bmQpOwp9CgppbnQgbWFpbih2b2lkKSB7CgljaGFyIHN0cltdID0gImFiYyI7CgkKCVByaW50U29ydGVkUGVybXV0YXRpb25zKHN0cik7CglyZXR1cm4gMDsKfQo=