home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 9 / 09.iso / e / e032 / 3.ddi / FILES / DISCRETE.PAK / PERMUTAT.M < prev    next >
Encoding:
Text File  |  1992-07-29  |  2.0 KB  |  89 lines
  1.  
  2. (* :Name: DiscreteMath`Permutations` *)
  3.  
  4. (* :Title: Elementary Operations on Permutaions
  5. *)
  6.  
  7. (*: Summary: This package contains various functions for doing elementary
  8. operations on permutations.
  9. *)
  10.  
  11. (* :Mathematica Version: 2.0 *)
  12.  
  13. (* Copyright 1988 Wolfram Research Inc. *)
  14.  
  15.         (** Elementary Operations on Permutations **)
  16.  
  17. BeginPackage["DiscreteMath`Permutations`"]
  18.  
  19. PermutationQ::usage =
  20.     "PermutationQ[e] yields True if e is a list representing a permutation."
  21.  
  22. ToCycles::usage =
  23.         "ToCycles[p] writes the permutation p as a list of cyclic
  24.         permutations."
  25.  
  26. FromCycles::usage =
  27.         "FromCycles[{p1,p2,..}] gives the permutation that corresponds to
  28.         a list of cycles."
  29.  
  30. RandomPermutation::usage =
  31.     "RandomPermutation[n] gives a random permutation of n elements."
  32.  
  33. Ordering::usage =
  34. "Ordering[list] gives the permutation that puts the elements of
  35. list in order."
  36.  
  37. Begin["`private`"]
  38.  
  39. PermutationQ[e_] := TrueQ[ Sort[e] == Range[Length[e]] ]
  40.  
  41. (**
  42. ToCycles[perm_?PermutationQ] :=
  43.     Block[{a, t, n, l, i, len},
  44.         len = Length[perm];
  45.         a = {} ;
  46.         t = Table[True, {len}];
  47.         For[i=1, i<=len, i++,
  48.             If[t[[i]], 
  49.                 For[n = perm[[i]]; l = {}, 
  50.                     t[[n]], 
  51.                     n = perm[[n]],
  52.                     t[[n]] = False; AppendTo[l, n]
  53.                    ];
  54.             AppendTo[a, l]
  55.             ]
  56.         ] ;
  57.         Return[a]
  58.     ]
  59. **)
  60.  
  61. ToCycles[perm_List] :=
  62.          Take[#, Position[Rest[#], First[#]] [[1,1]]]&  /@
  63.          Last[FoldList[
  64.                    If[MemberQ[Flatten[#1], #2], 
  65.                       #1,
  66.                       Append[#1, 
  67.                              NestList[perm[[#]]&, #2, Length[perm]]]]&,
  68.                    {}, perm]]
  69.  
  70.  
  71. FromCycles[cyc_List] :=
  72.            Last /@ Sort[Transpose[Flatten /@ {RotateRight /@ cyc, cyc}]]
  73.  
  74.  
  75. RandomPermutation[n_Integer?Positive] :=
  76.     Block[{t},
  77.         t = Array[{Random[], #} &, n];
  78.         t = Sort[t];
  79.         Map[ #[[2]] &, t ]
  80.     ]
  81.  
  82. Ordering[list_List] :=
  83.         Map[Last, Sort[Transpose[{list, Range[Length[list]]}]]]
  84.  
  85. End[]
  86. EndPackage[ ]
  87.  
  88. Null
  89.