|
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 Tue Apr 24, 2018 2:41 pm | All times are GMT
|
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
|
|