[GAP Forum] sorted index of group element

[Sandeep Murthy]

Hi,

If you wish to search for indices of group elements,
which are available via a sorted list using Elements( group ),
then, I think PositionSorted( sortedlist, elm ) would be
a faster way.  Here's an example for finding (1,2,3,4,5,6,7,8)
in SymmetricGroup( 8 ):

PositionSorted( Elements( SymmetricGroup( 8 ) ), (1,2,3,4,5,6,7,8) );
5914
gap> time;
31
Position( AsSortedList( SymmetricGroup( 8 ) ), (1,2,3,4,5,6,7,8) );
5914
gap> time;
386

Elements( group ) is sorted, and PositionSorted will use binary
search to find the element index, whereas Position can only use
linear search.

Sincerely, Sandeep.




Alexander Konovalov wrote:
> On 23 Feb 2013, at 19:02, Cotton Seed<cotton at alum.mit.edu>  wrote:
>
>> Is there way to get the sorted index of a group element?  More
>> specifically, let G be a group, and g an element of G.  Is there a function
>> that will give me the index i so that MagmaElement(G,i) = g?  Thanks!
>>
>> Best,
>> Cotton
>
>
> Dear Cotton,
>
> Let me first start with a hint how the source code of the MagmaElement
> function may be explored to find an answer, and then suggest a more
> efficient approach.
>
> First, looking at the code of MagmaElement function - this may be done by
> typing `ViewSource(MagmaElement);' in GAP - you may spot the call to
> AsSSortedList:
>
> InstallGlobalFunction( MagmaElement, function( M, i )
>     M:= AsSSortedList( M );
>     if Length( M )<  i then
>       return fail;
>     else
>       return M[i];
>     fi;
> end );
>
> Thus, MagmaElement returns the i-th element of AsSSortedList(M), where
> the latter contains all elements of M in strictly sorted order, w.r.t.
> the canonical ordering defined on M (depending on the type of M).
> Therefore, the index in which you're interested will be returned by
>
> Position( AsSSortedList( G ), g )
>
> For example,
>
> gap>  G:=SmallGroup(8,3);
> <pc group of size 8 with 3 generators>
> gap>  g:=Random(G);
> f1*f3
> gap>  s:=AsSSortedList(G);;
> gap>  Position(s,g);
> 6
> gap>  MagmaElement(G,6);
> f1*f3
> gap>  MagmaElement(G,6)=g;
> true
>
> Creating the list of all elements may not be very efficient, especially
> when the group is very large. However, if the method for `Enumerator'
> exists for such a group (see `?Enumerator), then there is another
> approach. Enumerator(G) need not to store its elements explicitly,
> but it knows how to determine the i-th element and the position of a
> given object. For example, this works:
>
> gap>  S:=SymmetricGroup(50);
> Sym( [ 1 .. 50 ] )
> gap>  g:=Random(S);
> (1,40,16,24,8,21,19,39,20,12,28,6)(2,5,49,3,45,4,30,25,13,11,47,44,36,9,50,43,
> 18,32)(7,46,22,15,35,41)(10,14,48,26,17)(23,42,33,29,37,38,27)
> gap>  enum:=Enumerator(S);
> <enumerator of perm group>
> gap>  pos:=Position(enum,g);
> 19748951512546719853008099372809900742253637283670495935197327991
> gap>  enum[pos]=g;
> true
>
> while AsSSortedList(S) will run out of memory. There are methods for
> enumerators of various types of algebraic structures defined in the
> GAP library.
>
> Please note that the order in which MagmaElement and Enumerator will
> sort elements of a domain sometimes may be different: the one for
> MagmaElement is determined by the '\<' relation defined on the domain,
> while the one for Enumerator depends on the algorithm used to enumerate
> elements of a domain of some particular type. For example,
>
> gap>  F:=FreeGroup("a","b");
> <free group on the generators [ a, b ]>
> gap>  AssignGeneratorVariables(F);
> #I  Assigned the global variables [ a, b ]
> gap>  G:=F/[a^32,b^2,b^-1*a*b*a];
> <fp group on the generators [ a, b ]>
> gap>  First([1..Size(G)],i ->  not MagmaElement(G,i)=Enumerator(G)[i]);
> 3
> gap>  MagmaElement(G,3);
> b
> gap>  Enumerator(G)[3];
> a^-1
>
> However, in most applications it is not the particular order that matters,
> but the ability to determine the position of an element in the fixed
> list of elements, and to retrieve the i-th element of that list.
>
> Hope this helps,
> Alexander
>
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum