[GAP Forum] Re: reply to GAP forum question

[Thomas Breuer]

Dear GAP Forum,

Laurent Bartholdi had asked for a special `Enumerator' method
for free magmas.

The GAP code below provides this.

All the best,
Thomas

#############################################################################
##
#M  Enumerator( <M> ) . . . . . . . . . . . . . . enumerator for a free magma
##
BindGlobal( "CATALAN", [ 1 ] );

BindGlobal( "Catalan", function( n )
    if not IsBound( CATALAN[n+1] ) then
      CATALAN[n+1]:= Binomial( 2*n, n ) / ( n+1 );
    fi;
    return CATALAN[n+1];
end );

BindGlobal( "ElementNumber_FreeMagma", function( enum, nr )
    local WordFromInfo, n, l, summand, NB, q, p;

    # Create the external representation (recursively).
    WordFromInfo:= function( N, l, p, q )
      local k, NB, summand, Nk, p1, p2, q1, q2;;

      if l = 1 then
        return p;
      fi;

      k:= 0;
      while 0 < q do
        k:= k+1;
        NB:= Catalan( l-k-1 );
        summand:= Catalan( k-1 ) * NB;
        q:= q - summand;
      od;
      q:= q + summand;

      Nk:= N^k;
      p1:= p mod Nk;
      if p1 = 0 then
        p1:= Nk;
      fi;
      p2:= ( p - p1 ) / Nk + 1;

      q2:= q mod NB;
      if q2 = 0 then
        q2:= NB;
      fi;
      q1:= ( q - q2 ) / NB + 1;

      return [ WordFromInfo( N, k,   p1, q1 ),
               WordFromInfo( N, l-k, p2, q2 ) ];
    end;

    n:= enum!.nrgenerators;

    l:= 0;
    while 0 < nr do
      NB:= Catalan( l );
      l:= l+1;
      summand:= n^l * NB;
      nr:= nr - summand;
    od;
    nr:= nr + summand;

    q:= nr mod NB;
    if q = 0 then
      q:= NB;
    fi;

    p:= ( nr - q ) / NB + 1;

    return ObjByExtRep( enum!.family, WordFromInfo( n, l, p, q ) );
end );

BindGlobal( "NumberElement_FreeMagma", function( enum, elm )
    local WordInfo, n, info, pos, i;

    if not IsCollsElms( FamilyObj( enum ), FamilyObj( elm ) ) then
      return fail;
    fi;

    # Analyze the structure (recursively).
    WordInfo:= function( ngens, obj )
      local info1, info2, N;

      if IsInt( obj ) then
        return [ ngens, 1, obj, 1 ];
      else
        info1:= WordInfo( ngens, obj[1] );
        info2:= WordInfo( ngens, obj[2] );
        N:= info1[2] + info2[2];
        return [ ngens, N,
                 info1[3]+ ngens^info1[2] * ( info2[3]-1 ),
                 Sum( List( [ 1 .. info1[2]-1 ],
                      i -> Catalan( i-1 ) * Catalan( N-i-1 ) ), 0 )
                 + ( info1[4] - 1 ) * Catalan( info2[2]-1 ) + info2[4] ];
      fi;
    end;

    # Calculate the length, the number of the corresponding assoc. word,
    # and the number of the bracketing.
    n:= enum!.nrgenerators;
    info:= WordInfo( n, ExtRepOfObj( elm ) );

    # Compute the position.
    pos:= 0;
    for i in [ 1 .. info[2]-1 ] do
      pos:= pos + n^i * Catalan( i-1 );
    od;
    return pos + ( info[3] - 1 ) * Catalan( info[2]-1 ) + info[4];
end );

InstallMethod( Enumerator,
    "for a free magma",
    [ IsWordCollection and IsWholeFamily and IsMagma ],
    function( M )

    # A free associative structure needs another method.
    if IsAssocWordCollection( M ) then
      TryNextMethod();
    fi;

    return EnumeratorByFunctions( M, rec(
               ElementNumber := ElementNumber_FreeMagma,
               NumberElement := NumberElement_FreeMagma,

               family       := ElementsFamily( FamilyObj( M ) ),
               nrgenerators := Length( ElementsFamily( 
                                           FamilyObj( M ) )!.names ) ) );
    end );