--- perm.spad.pamphlet 2006-06-04 12:36:44.000000000 +0200 +++ perm.spad.pamphlet.alt 2006-06-04 12:01:23.000000000 +0200 @@ -60,7 +60,7 @@ )abbrev domain PERM Permutation ++ Authors: Johannes Grabmeier, Holger Gollan ++ Date Created: 19 May 1989 -++ Date Last Updated: 2 June 2006 +++ Date Last Updated: 24 May 1991 ++ Basic Operations: _*, degree, movedPoints, cyclePartition, order, ++ numberOfCycles, sign, even?, odd? ++ Related Constructors: PermutationGroup, PermutationGroupExamples @@ -96,16 +96,13 @@ ++ listRepresentation(p) produces a representation {\em rep} of ++ the permutation p as a list of preimages and images, i.e ++ p maps {\em (rep.preimage).k} to {\em (rep.image).k} for all - ++ indices k. Elements of \spad{S} not in {\em (rep.preimage).k} - ++ are fixed points, and these are the only fixed points of the - ++ permutation. + ++ indices k. coercePreimagesImages : List List S -> % ++ coercePreimagesImages(lls) coerces the representation {\em lls} ++ of a permutation as a list of preimages and images to a permutation. - ++ We assume that both preimage and image do not contain repetitions. coerce : List List S -> % ++ coerce(lls) coerces a list of cycles {\em lls} to a - ++ permutation, each cycle being a list with no + ++ permutation, each cycle being a list with not ++ repetitions, is coerced to the permutation, which maps ++ {\em ls.i} to {\em ls.i+1}, indices modulo the length of the list, ++ then these permutations are mutiplied. @@ -159,24 +156,13 @@ ++ whose image is given by {\em ls} and the preimage is fixed ++ to be {\em [1,...,n]}. ++ Note: {coerceImages(ls)=coercePreimagesImages([1,...,n],ls)}. - ++ We assume that both preimage and image do not contain repetitions. private ==> add -- representation of the object: Rep := V L S -@ - -We represent a permutation as two lists of equal length representing preimages -and images of moved points. I.e., fixed points do not occur in either of these -lists. This enables us to compute the set of fixed points and the set of moved -points easily. -Note that this was not respected in versions before [[patch--50]] of this -domain. - -<>= -- import of domains and packages import OutputForm @@ -281,35 +267,9 @@ s : RECPRIM := [p.1,p.2] coercePreimagesImages preImageAndImage == - preImage: List S := [] - image: List S := [] - for i in preImageAndImage.1 - for pi in preImageAndImage.2 repeat - if i ~= pi then - preImage := cons(i, preImage) - image := cons(pi, image) - - [preImage, image] -@ - -This operation transforms a pair of preimages and images into an element of the -domain. Since we assume that fixed points do not occur in the representation, -we have to sort them out here. - -Note that before [[patch--50]] this read -\begin{verbatim} - coercePreimagesImages preImageAndImage == p : % := [preImageAndImage.1,preImageAndImage.2] -\end{verbatim} -causing bugs when computing [[movedPoints]], [[fixedPoints]], [[even?]], -[[odd?]], etc., as reported in Issue~\#295. - -The other coercion facilities check for fixed points. It also seems that [[*]] -removes fixed points from its result. -<>= - - movedPoints p == construct p.1 + movedPoints p == construct p.1 --check on fixed points !! degree p == #movedPoints p @@ -454,22 +414,14 @@ coerceImages (image) == preImage : L S := [i::S for i in 1..maxIndex image] - coercePreimagesImages [preImage,image] -@ - -Up to [[patch--50]] we did not check for duplicates. + p : % := [preImage,image] -<>= if S has Finite then coerceImages (image) == preImage : L S := [index(i::PI)::S for i in 1..maxIndex image] - coercePreimagesImages [preImage,image] -@ - -Up to [[patch--50]] we did not check for duplicates. + p : % := [preImage,image] -<>= fixedPoints ( p ) == complement movedPoints p cyclePartition p ==