For the sake of simplicity assume that one permutation is identity permutation and the other one is pi. Write pi as product of disjoint cycles, which can be done in O(n) time. If the number of disjoint cycles is k, then the distance between identity permutation and pi is (n - k). Proof of correctness is by induction on number of cycles.
thx aj --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
