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

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>