Given a string, print all permutations of it in sorted order.
We can optimize step 4 of the above algorithm for finding next permutation. Instead of sorting the subarray after the ‘first character’, we can reverse the subarray, because the subarray we get after swapping is always sorted in non-increasing order. This optimization makes the time complexity as O(n x n!).
Read full article from Print all permutations in sorted (lexicographic) order | GeeksforGeeks
1. Sort the given string in non-decreasing order and print it. The first permutation is always the string sorted in non-decreasing order.
2. Start generating next higher permutation. Do it until next higher permutation is not possible. If we reach a permutation where all characters are sorted in non-increasing order, then that permutation is the last permutation.
Steps to generate the next higher permutation:
1. Take the previously printed permutation and find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘first character’.
1. Take the previously printed permutation and find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘first character’.
2. Now find the ceiling of the ‘first character’. Ceiling is the smallest character on right of ‘first character’, which is greater than ‘first character’. Let us call the ceil character as ‘second character’.
3. Swap the two characters found in above 2 steps.
4. Sort the substring (in non-decreasing order) after the original index of ‘first character’.
Time Complexity: O(n^2 x n!)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 chracter, 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 );
}
}
}
We can optimize step 4 of the above algorithm for finding next permutation. Instead of sorting the subarray after the ‘first character’, we can reverse the subarray, because the subarray we get after swapping is always sorted in non-increasing order. This optimization makes the time complexity as O(n x n!).
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 chracter, 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] );
// reverse the string on right of 'first char'
reverse( str, i + 1, size - 1 );
}
}
}