Author 
Message 
vb.here@gmail.com science forum beginner
Joined: 05 Apr 2006
Posts: 1

Posted: Wed Apr 05, 2006 10:16 am Post subject:
Finding the distance between two permutations of a string of length N



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 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Wed Apr 05, 2006 10:29 pm Post subject:
Re: Finding the distance between two permutations of a string of length N



vb.here@gmail.com wrote:
Quote:  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

There was a thread related to this very topic a few days ago in
sci.math, called "Decomposition of a permutation into a product of
transpositions". The whole thread can be read at
http://groups.google.com/group/sci.math/browse_frm/thread/81221837dfb32b30/6f37517a56988eaf?lnk=st&q=permutation&rnum=19#6f37517a56988eaf
..
 Christopher Heckman
P.S. If you're going to post the same question in two newsgroups, post
it in both newsgroups at the same time. That way, responses from one
group will show up in the other(s). 

Back to top 


Google


Back to top 



The time now is Mon Jun 18, 2018 4:10 am  All times are GMT

