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
permutation swap distance
Posted: Aug 26, 2013 3:37 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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



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.