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 [email protected].
