Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 Michal Kvasnicka Posts: 62 Registered: 5/7/10
Re: permutation swap distance
Posted: Aug 26, 2013 8:00 AM

"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:
>
>
> 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

Date Subject Author
8/26/13 Michal Kvasnicka
8/26/13 Michal Kvasnicka
8/26/13 Bruno Luong
8/26/13 Michal Kvasnicka