[GAP Forum] length
Goetz Pfeiffer
goetz at schmidt.nuigalway.ie
Mon Mar 29 11:19:48 BST 2004
Dear Forum, dear marcus,
On Sun, 2004-03-28 at 06:00, marcus at thunder.realcool.org wrote:
> How can I compute the
> length of an element
> of a group, where by
> "length" I mean the minimum
> number of generators
> needed to write the element,
> assuming that I've fixed
> a generating set for the group.
> In particular, I need to do
> this for the symmetric group
> using generating set
> (1,2), (2,3), (3,4), ... (n-1,n)
the length of a permutation p with respect to
the generating set { (i, i+1) } is the number of pairs
i < j with i^p > j^p. It can for example be computed
by this function LengthPerm:
gap> LengthPerm:= p ->
> Sum([1..LargestMovedPoint(p)], j-> Number([1..j-1], i-> i^p > j^p));
function( p ) ... end
gap> LengthPerm((1,2,3,4,5));
4
gap> Collected(List(Elements(SymmetricGroup(4)), LengthPerm));
[ [ 0, 1 ], [ 1, 3 ], [ 2, 5 ], [ 3, 6 ], [ 4, 5 ], [ 5, 3 ], [ 6, 1 ] ]
In general, the computation of the length of a
group element is less straight forward.
Goetz Pfeiffer.
-------------------------------------------------------------------------
Goetz.Pfeiffer at NUIGalway.ie http://schmidt.nuigalway.ie/~goetz/
National University of Ireland, Galway. phone +353-91-512027 (x3591)
More information about the Forum
mailing list