FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
Finding the distance between two permutations of a string of length N
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
Author Message
vb.here@gmail.com
science forum beginner


Joined: 05 Apr 2006
Posts: 1

PostPosted: Wed Apr 05, 2006 10:16 am    Post subject: Finding the distance between two permutations of a string of length N Reply with 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
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Wed Apr 05, 2006 10:29 pm    Post subject: Re: Finding the distance between two permutations of a string of length N Reply with quote
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
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
The time now is Tue Apr 24, 2018 2:41 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group

[ Time: 0.0344s ][ Queries: 16 (0.0029s) ][ GZIP on - Debug on ]