top of page

## program solution

// Program to print all permutations of a string in sorted order.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

/* Following function is needed for library function qsort(). */

int compare (const void *a, const void * b)

{

return ( *(char *)a - *(char *)b );

}

// A utility function two swap two characters a and b

void swap (char* a, char* b)

{

char t = *a;

*a = *b;

*b = t;

}

/* This function finds the index of the smallest character which is greater than 'first' and is present in str[l..h] */

int findCeil (char str[], char first, int l, int h)

{

// initialize index of ceiling element

int ceilIndex = l;

/* Now iterate through rest of the elements and find the smallest character greater than 'first' */

for (int i = l+1; i <= h; i++)

if (str[i] > first && str[i] < str[ceilIndex])

ceilIndex = i;

return ceilIndex;

}

// Print all permutations of str in sorted order

void sortedPermutations ( char str[] )

{

// Get size of string

int size = strlen(str);

// Sort the string in increasing order

qsort( str, size, sizeof( str[0] ), compare );

// Print permutations one by one

bool isFinished = false;

while ( ! isFinished )

{

// print this permutation

printf ("%s \n", str);

// Find the rightmost character which is smaller than its next character. Let us call it 'first char'

int i;

for ( i = size - 2; i >= 0; --i )

if (str[i] < str[i+1])

break;

/* If there is no such character, all are sorted in decreasing order, means we just printed the last permutation and we are done. */

if ( i == -1 )

isFinished = true;

else

{

/* Find the ceil of 'first char' in right of first character. Ceil of a character is the smallest character greater than it */

int ceilIndex = findCeil( str, str[i], i + 1, size - 1 );

// Swap first and second characters

swap( &str[i], &str[ceilIndex] );

// Sort the string on right of 'first char'

qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );

}

}

}

// Driver program to test above function

int main()

{

char str[] = "ABCD";

sortedPermutations( str );

return 0;

}

ABCD

ABDC

....

....

DCAB

DCBA

bottom of page