Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



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



