Let the string be str1. Sort that string and form a map of sorted string and their positions in the original string .
example :consider string "computer"
sorted map will contain
c 1
e 7
m 3
o 2
p 4
r 8
t 6
u 5
Let the permuted string be "comtepur"
Now compare the permuted string with the original input string. Compare the character one by one. I
nitialiase a counter to 0.
When the character permuted string is same as the original one do not increment the counter.
When it is different (let the position of that character in permuted string be i), search the character in the sorted array using binary sort and find its value ie. its position in the original string(let it be j).
Now swap the characters at i and j in the original string and increment the counter.
Continue this process till end of string is reached.
Now the counter gives the distance between two permutations.
So in our case when i = 4:
it is different. In the map the value for t = 6. So swap 4th and 6th positions. the input now changes to "comtuper" and counter becomes 1. Continue this for next character and the counter becomes 2.
It is not altered for remaining 3 characters as they match with the input string.
So the distance is 2
Since we use binary search to lacate the position of character to be swapped the time complexity is o(nlog(n))
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
- [algogeeks] Finding the distance between two permutations of ... vb
- [algogeeks] Re: Finding the distance between two permuta... Vishal
- [algogeeks] Re: Finding the distance between two permuta... vishnu priya
