Date: Aug 26, 2013 3:37 AM
Author: Michal Kvasnicka
Subject: permutation swap distance

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

===============================================================
So far I am using the following function swapdist, which is based on fact, that the swap distance corresponds to the number of exchanges in a bubblesort.

function ds = swapdist(x,y)
[~,dsx] = bubbleSort(x);
[~,dsy] = bubbleSort(y);
ds = abs(dsx-dsy);
end %dswap

function [list, nswaps] = bubbleSort(list)
hasChanged = true;
itemCount = numel(list);
nswaps = 0;
while(hasChanged)
hasChanged = false;
itemCount = itemCount - 1;
for index = (1:itemCount)
if(list(index) > list(index+1))
list([index index+1]) = list([index+1 index]); %swap
hasChanged = true;
nswaps = nswaps + 1;
end %if
end %for
end %while
end %bubbleSort
===============================================================