Hi I am reading a algorithm book , and I found an algorithm that
generate permutations using the lexicographic ordering method.
I have read that comments and clear what's going on but I cannot
underestand the code in that book.
book code
[code]
template <class TYPE>
template <class TYPE>
void Permute_in_book (TYPE arr[] , int n , int s = 0 )
{
TYPE tmp ;
int t , p , q ;
Print (arr , n );
if ( s >= n -1 )
return ;
for ( p = n-2 ; p>=s ; p--)
{
for ( q= p+1 ; q < n ; q++)
{
// Swap elements p and q
tmp = arr[p] ;
arr[p] = arr[q] ;
arr[q] = tmp ;
Permute_in_book (arr , n , p+1);
}
// Use left rotation from p to n - 1 to restore the order
q--; t = p ; tmp = arr[t];
while ( t != q )
{
arr [t] = arr [t+1] ;
t++;
}
arr[t] = tmp ;
}
}
[/code]
I really get a hard time when I try to underestand this code. Finally
I feel
like that I need some expertise help here. But before asking that I
write my
own function. well according to the comments and the details in the
book, It's easy to construct my own algorithm, But it so different
from the book's one.
This is my code.
[code]
void Permute ( TYPE arr[] , int n , int s = 0 )
// Generate all premutations , in lexicographic order, of the right-
hand
// subset of the array starting at the offset s , Using s = 0
generates
// Permutations for the whole array of length n. When the function
// finishes, the array is restroed to it's original order
{
TYPE tmp ;
int t , p, q ;
if ( s == n-1)
// then print it
{
Print ( arr , n);
return ;
}
p = s;
Permute ( arr , n, p+1);
for ( q = s +1; q < n ; q++)
{
tmp = arr [p] ;
arr [p] = arr [q];
arr [q] = tmp ;
Permute ( arr , n , p+1) ;
}
tmp = arr [s] ;
for ( int i = s ; i < n-1 ;i++)
{
arr[i] = arr[i+1] ;
}
arr[n-1] = tmp ;
}
[/code]
I run both codes using microsoft Visual Studio 6.0 . They gives same
results.
Yes , that means there is nothing something wrong in the book. Anyway
book also
explains like this
[quote]
Even through it's easy to reason about
this algorithm top-down , using a bottom-up
implementation is more efficient, as shown in the
following Permute() function.
[/quote]
well I go more visits on the wiki and google about this subject. But I
unable to
find out what's going on there with those bootm-up and top-down
implementations related to this ?
please post me a link or by your words about the algorithm's ( I mean
book's code) detail in detail.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
