following is code from geeks for geeks.
Please tell how the complexity of this in n*n!
n*n! times loop will be executed and then wat about the statements in
loop....??
reference:-
http://www.geeksforgeeks.org/lexicographic-permutations-of-string/(second
method)
void reverse(char str[], int l, int h)
{
while (l < h)
{
swap(&str[l], &str[h]);
l++;
h--;
}
}
// 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] );
// reverse the string on right of 'first char'
reverse( str, i + 1, size - 1 );
}
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
