> < ^ Date: Tue, 01 Oct 2002 17:31:06 +0100
< ^ From: Christopher Jefferson <caj@cs.york.ac.uk >
> < ^ Subject: Re: Complexity of group problem
At 02:13 PM 9/30/02 +0200, you wrote:
>Dear Gap-forum, and Christopher Jefferson,
>
> > I am dealing with a problem where I have a permutation group G defined 
> over
> > the integers 1...n, generated by a set of generators S
> >
> > I want to find orbit(1), orbit(2) in "stabilizer of 1", orbit(3) in
> > "stabilizer of 1 and stabilizer of 2", etc.
>
>OrbitList:=function(S,n)
>         local g,i,l;
>         g:=Group(S); l:=[];
>         for i in [1..n] do
>                 Append(l,[Orbit(g,i)]);
>                 g:=Stabilizer(g,i);
>         od;
>         return l;
>end;
>
>For example:
>gap> OrbitList([(1,2,3),(2,4)],4);
>[ [ 1, 2, 3, 4 ], [ 2, 4, 3 ], [ 3, 4 ], [ 4 ] ]
>
>Best regards,
>
>   Jan

Thank you, this algorithm returns exactly what I want, and seems to do it
at lightening speed for any group I care to give it :)
However, for "neatness" of my paper, it would be nice to be able to write
that this took polynomial time in n and the number of generators of S I
give... could anyone tell me if I can indeed write this, or where I could
start looking to find out if I can write this?

Thank you all for lots of useful replies!

Chris


> < [top]