MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

Distance between permutations

I'm looking for a way of determining the minimum number of transpositions
between two permutations. It is easy to determine the number of pairwise
transpositions needed to go from the identity permutation to another
permutation P as, say

In[1]:= Needs["DiscreteMath`Combinatorica`"];
In[2]:= p = {3, 2, 5, 1, 6, 4};
In[3]:= c=ToCycles[p]
Out[3]:= {{3, 5, 6, 4, 1}, {2}}
In[4]:= 6-Length[c]
Out[4]:= 4

which is the number of transpositions needed to change {1,2,3,4,5,6} to

But I would like to know the "distance" between {'s','p','o','t'} and
{'t','o','p','s'}, or between {'a','g','h','p','n'} some other permutation

I can do it by using a Replace rule like {'s'->1,'p'->2,'o'->3,'t'->4} and
going from there, but I don't know how to generalise my little routine to
handle *any* length (rather than just, say, length-4). And I wondered if
there is a way of avoiding converting the first permutation into the "basis
permutation" with my use of the Replace rules (Please excuse the ad-hoc

  • Prev by Date: Re: Diophantine Equations
  • Next by Date: Re: Solve[wave equation,bound.cond.]
  • Previous by thread: Filtered Backprojection
  • Next by thread: Re: Distance between permutations