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
permutation swap distance
Posted: Aug 26, 2013 3:37 AM

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

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