Dear forum,

Javaid Aslam asked:

I am trying to see if somebody has a routine for
factoring a given permutation cycle into a product of the
the transpositions (cycles of length 2);
e.g., the cycle (1,2,3,4) factors into (3,4)*(2,3)*(1,2).

The following function will decompose any permutation pi into a product of
transpositions.

TranspositionDecompositionPerm := function (pi)

local res, cycle, start, pnt;

res := [];

while pi <> () do

# compute decomposition of cycle starting
#with smallest moved point

cycle := [];
start := SmallestMovedPointPerm (pi);
pnt := start^pi;

# now get the decomposition
# (p_1, p_2, ..., p_n) = (p_1, p_2)(p_1, p_3)...(p_1, p_n)

repeat
Add (cycle, (start, pnt));
pnt := pnt^pi;
until pnt = start;

# multiply pi by the inverse of the cycle
pi := pi * Product (Reversed (cycle));

# add the decompositio of that cyclie to the result
Add (res, cycle);

od;
return res;
end;

Note that TranspositionDecompositionPerm returns lists of lists of
transpositions, each sublist corresponding to one disjoint cycle of pi.
Note that, as it stands, the function below is not suitable for large
permutations because the storage required for each transposition (s,t) is
roughly proportional to the maximum of s and t. (Thus an obvious
improvement would be to just return the pairs [s,t] instead of the
transpositions themselves).

Hope this helps,

Burkhard.

______________________________________________________________________________
Dr. Burkhard Höfling               Phone: (02) 6249 3995, int. +61 2 6249 3995
School of Mathematical Sciences    Fax:   (02) 6249 5549, int. +61 2 6249 5549
Australian National University     email: Burkhard.Hofling@maths.anu.edu.au
Canberra ACT 0200, Australia       WWW:   http://wwwmaths.anu.edu.au/~hofling

Miles-Receive-Header: reply