[GAP Forum] sorted index of group element

[Alexander Konovalov]

Thanks for the remark about PositionSorted, Sandeep. However, I think in this example 
the difference is not coming from PositionSorted vs Position, but from AsSSortedList 
vs AsSortedList:

gap> PositionSorted( AsSSortedList( SymmetricGroup( 8 ) ), (1,2,3,4,5,6,7,8) );time;
5914
26
gap> PositionSorted( AsSortedList( SymmetricGroup( 8 ) ), (1,2,3,4,5,6,7,8) );time;
5914
371

gap> Position( AsSSortedList( SymmetricGroup( 8 ) ), (1,2,3,4,5,6,7,8) );time;
5914
25
gap> Position( AsSortedList( SymmetricGroup( 8 ) ), (1,2,3,4,5,6,7,8) );time;
5914
402

First, Elements is an outdated synonym for `AsSSortedList':

gap> Print(Elements);
function ( coll )
    Info( InfoPerformance, 2, "`Elements' is an outdated synonym for `AsSSortedList'" );
    Info( InfoPerformance, 2, "If sortedness is not required, `AsList' might be much faster!" );
    return AsSSortedList( coll );
end

Second, it is AsSortedList which takes most of the time in your example:

gap> AsSortedList( SymmetricGroup( 8 ) );;time;
362
gap> AsSSortedList( SymmetricGroup( 8 ) );;time;
24

The manual indeed says that "PositionSorted" uses binary search, whereas 
Position can in general use only linear search", however, in the case 
which we have now, Position is 'cleverer' that advised and it recognises 
that the argument is sorted. 

The remaining question is: why AsSortedList takes much longer than AsSSortedList?

The former calls SortedList which returns a new mutable and dense list:

gap> Print(ApplicableMethod(AsSortedList, [ SymmetricGroup( 8 ) ]));
function ( l )
    local  s;
    s := SortedList( l );
    MakeImmutable( s );
    return s;
end

Exploring the call stack further, you will also see calls to List and Sort,
and then finally Enumerator will be called to enumerate elements of the group.
Copying data etc. will take some time, while the latter method uses an 
immediate approach:

gap> Print(ApplicableMethod(AsSSortedList, [ SymmetricGroup( 8 ) ]));
function ( G )
    return ElementsStabChain( StabChainMutable( G ) );
end
gap> 

Best,
Alexander


On 25 Feb 2013, at 20:38, Sandeep Murthy <sandeepr.murthy at gmail.com> wrote:

> 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