Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Software » comp.soft-sys.matlab

Topic: permutation swap distance
Replies: 3   Last Post: Aug 26, 2013 8:00 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Michal Kvasnicka

Posts: 62
Registered: 5/7/10
Re: permutation swap distance
Posted: Aug 26, 2013 8:00 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kvfdsp$434$1@newscl01ah.mathworks.com>...
> "Michal Kvasnicka" wrote in message <kvf0j4$e9r$1@newscl01ah.mathworks.com>...
> > I am looking for effective (algoritmically fastest) implementation of swap distance metric algorithm for two permutations.
> >
> > Example:
> > perm1 = [ 1 2 3]
> > perm2 = [ 3 2 1]
> >
> > swapdist(perm1,perm2) = 3
> >
> > because
> > 1 2 3 -> 2 1 3 -> 2 3 1 -> 3 2 1 (3 neighbor elements swaps)
> >
> > Any hints?
> >
> > Michal

>
> See my code in this thread:
>
> http://www.mathworks.com/matlabcentral/newsreader/view_thread/239871
>
> Bruno

Your swapindex function is able to find every atomic swaps between [1:n] and P permutations (not only neighbors swaps!!!), when I want to only count them I create more simpler function:

function di = intchngdist(p1,p2)
% interchange distance of two permutations p1 and p2
n = length(p1);
di = 0;
for i=1:n
while p1(i) ~= p2(i)
j = find(p1==p2(i));
p2([i j]) = p2([j i]); % interchange i and j
di = di + 1;
end
end
end %intchngdist



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.