Re: Distance between permutations

*To*: mathgroup at smc.vnet.net*Subject*: [mg21627] Re: [mg21547] Distance between permutations*From*: Hartmut Wolf <hwolf at debis.com>*Date*: Tue, 18 Jan 2000 02:35:15 -0500 (EST)*Organization*: debis Systemhaus*References*: <200001150703.CAA06285@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

DIAMOND Mark schrieb: > > 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!) As I understand your problem is to generate the replace rule in general. Perhaps this will help you: In[1]:= symbols = {"s", "p", "o", "t"} Out[1]= {"s", "p", "o", "t"} Now if In[2]:= Length[symbols] == Length[Union[symbols]] Out[2]= True then you can build In[3]:= convertRule = MapThread[Rule, {symbols, Range[Length[symbols]]}] Out[3]= {"s" -> 1, "p" -> 2, "o" -> 3, "t" -> 4} In[4]:= reconvertRule = Reverse /@ convertRule Out[4]= {1 -> "s", 2 -> "p", 3 -> "o", 4 -> "t"} Kind regards, Hartmut

**References**:**Distance between permutations***From:*"DIAMOND Mark" <noname@noname.com>