> < ^ From:

> < ^ Subject:

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 pointcycle := [];

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

> < [top]