Distance between permutations

*To*: mathgroup at smc.vnet.net*Subject*: [mg21547] Distance between permutations*From*: "DIAMOND Mark" <noname at noname.com>*Date*: Sat, 15 Jan 2000 02:03:54 -0500 (EST)*Organization*: The University of Western Australia*Sender*: owner-wri-mathgroup at wolfram.com

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 {3,2,5,1,6,4}. 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 thereof. 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 terminology!)

**Follow-Ups**:**Re: Distance between permutations***From:*Ken Levasseur <Kenneth_Levasseur@uml.edu>

**Re: Distance between permutations***From:*Hartmut Wolf <hwolf@debis.com>