Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2000
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2000

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

Search the Archive

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


  • Prev by Date: Help! Mathematica on my 500MHz outperforms my GHz machine!
  • Next by Date: Re: Series expansion of ArcSin around 1
  • Previous by thread: Distance between permutations
  • Next by thread: Re: Distance between permutations