Search   Memberlist   Usergroups
 Page 1 of 1 [2 Posts]
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
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
..

--- 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).

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [2 Posts]
 The time now is Mon Dec 17, 2018 5:43 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Instantaneous Action at a Distance Phil Gardner Research 1 Mon Jul 17, 2006 3:32 pm Finding a Web Design Development with a Good Results lbardagol@gmail.com Math 0 Mon Jul 17, 2006 10:21 am distance matrix consolidation bird Math 6 Sat Jul 15, 2006 9:05 pm Tied Up & Strung Out: Hollywood String Theory Movie!!! Lo... jollyrogership@yahoo.com1 Math 7 Sat Jul 15, 2006 4:53 pm Apparent Bug In "Permutations" Function In Maxima 5.9.3 Mark Lawton Symbolic 2 Sat Jul 15, 2006 11:31 am