Here we assume -
n = number of chars which are out of place in the permutations
N = actual length of string.
Let's define perfect swap as the swap in which both the characters are placed at the desired location. For a string with n out of place characters, with no perfect swaps, takes (n-1) swaps to convert. i.e. the distance between two permutations is (n-1).
Now, if there is only one perfect swap possible, then the distance is
= 1 (for perfect swap) + (n-3) (for rest n-2 characters, without any perfect swaps)
= n-2.
Generalizing this, for two permutations of string, with n out of place characters, with p perfect swaps, the distance is
= p + (n-2p-1)
= n - p - 1
(If n==2p, then the answer is p. Hence more genralized _expression_ is
distance = p + ( n - 2p > 0 ? n - 2p - 1 : n - 2p )
So the problem reduces to finding number of out of place characters (n) and then finding number of perfect swaps (p).
1. n can be found in O(N). (N be the length of string)
2. For finding p,
i. Create an array with out of place character pairs where first char is from first string and 2nd char is from permuted string. e.g . in the given example, we will have elements of this array as "ac", "bd", "cb", "da". Length of this array is n.
ii. Sort this array. - O(n log n)
iii. For each element search whether the reverse string is present in the array. - O(n log n).
iv. If the reverse string is found, it is a perfect swap. hence, p++.
So, complexity of finding p is O(n log n) ~ O( N log N).
Once we found n and p, we can find the distance from the formula. The overall complexity is O (N log N).
Let me know if I am missing something.
~Vishal
On 4/5/06, vb <[EMAIL PROTECTED]> wrote:
Hi,
I need to find distance between two permutations of a string of length
N. Distance in this case is defined as the minimum number of swaps
needed to convert one permutation into another. Can somebody help me
out with it. The expected order of complexity is O(N.log(N)).
Eg: With two permutations as : abcd, cdba . The distance is 3 as min 3
swaps are required to convert one into another.
abcd(swap a and c) -> cbad(swap d and b) -> cdab(swap b and a)-> cdba
--
Vishal Padwal
Tel : 631-645-1406
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
