(* :Name: DiscreteMath`Permutations` *)

(* :Title: Elementary Operations on Permutations
*)

(* :Summary:
This package contains various functions for doing elementary
operations on permutations.
*)

(* :Package Version: 1.0 *)

(* :Mathematica Version: 2.0 *)

(* :Copyright: Copyright 1988-1999, Wolfram Research Inc. *)

		(** Elementary Operations on Permutations **)

BeginPackage["DiscreteMath`Permutations`"]

PermutationQ::usage =
"PermutationQ[p] yields True if p is a list representing a permutation and
False otherwise."

ToCycles::usage =
"ToCycles[p] gives the cycle structure of permutation p,
as a list of cyclic permutations."

FromCycles::usage =
"FromCycles[{c1,c2,...}] gives the permutation that has the given 
cycle structure." (* cycle structure = cyclic decomposition *)

RandomPermutation::usage =
"RandomPermutation[n] gives a random permutation of n elements."

Ordering::usage =
"Ordering[list] gives the permutation that puts the elements of
list in order."

Begin["`Private`"]

PermutationQ[e_] := (Sort[e] === Range[Length[e]])

(** 
ToCycles[perm_?PermutationQ] :=
	Block[{a, t, n, l, i, len},
		len = Length[perm];
		a = {} ;
		t = Table[True, {len}];
		For[i=1, i<=len, i++,
			If[t[[i]], 
				For[n = perm[[i]]; l = {}, 
					t[[n]], 
					n = perm[[n]],
					t[[n]] = False; AppendTo[l, n]
				   ];
			AppendTo[a, l]
			]
		] ;
		Return[a]
	]
**)

ToCycles[perm_List] :=
         Take[#, Position[Rest[#], First[#]] [[1,1]]]&  /@
         Last[FoldList[
                   If[MemberQ[Flatten[#1], #2], 
                      #1,
                      Append[#1, 
                             NestList[perm[[#]]&, #2, Length[perm]]]]&,
                   {}, perm]]


FromCycles[cyc_List] :=
           Last /@ Sort[Transpose[Flatten /@ {RotateRight /@ cyc, cyc}]]


RandomPermutation[n_Integer?Positive] :=
	Block[{t},
		t = Array[{Random[], #} &, n];
		t = Sort[t];
		Map[ #[[2]] &, t ]
	]

Ordering[list_List] :=
        Map[Last, Sort[Transpose[{list, Range[Length[list]]}]]]

End[]
EndPackage[ ]

Null
