stdgen.gi

GAP源码

#############################################################################
##
#W  stdgen.gi                GAP library                        Thomas Breuer
##
#H  @(#)$Id: stdgen.gi,v 1.1 2002/02/20 17:21:29 gap Exp $
##
#Y  (C) 1999 School Math and Comp. Sci., University of St.  Andrews, Scotland
##
##  This file contains the implementations needed for dealing with standard
##  generators of finite groups.
##
Revision.stdgen_gi :=
    "@(#)$Id: stdgen.gi,v 1.1 2002/02/20 17:21:29 gap Exp $";


#############################################################################
##
#F  HumanReadableDefinition( <info> )
##
InstallGlobalFunction( HumanReadableDefinition, function( info )

    local nrgens,
          alpha,
          lalpha,
          generators,
          i,
          m,
          gensstring,
          nraux,
          auxnames,
          description,
          script,
          len,
          line,
          word,
          pos,
          str,
          j,
          strline,
          linelen;

    # Check the argument.
    if not ( IsRecord( info ) and IsBound( info.script ) ) then
      Error( "<info> must be a record with a component `script'" );
    elif not IsBound( info.description ) then

      # Get names of the standard generators.
      alpha:= [ "a","b","c","d","e","f","g","h","i","j","k","l","m",
                "n","o","p","q","r","s","t","u","v","w","x","y","z" ];
      lalpha:= Length( alpha );
      if not IsBound( info.generators ) then

        nrgens:= Number( info.script,
                         line -> Length( line ) <= 3 and IsInt( line[2] ) );
        generators:= [];
        for i in [ 1 .. nrgens ] do
          if i <= lalpha then
            generators[i]:= alpha[i];
          else
            m:= (i-1) mod lalpha + 1;
            generators[i]:= Concatenation( alpha[m],
                                           String( ( i - m ) / lalpha ) );
          fi;
        od;

        gensstring:= "";
        for i in generators do
          Append( gensstring, i );
          Append( gensstring, ", " );
        od;
        Unbind( gensstring[ Length( gensstring ) ] );
        Unbind( gensstring[ Length( gensstring ) ] );
        info.generators:= gensstring;

      else

        gensstring:= info.generators;
        generators:= SplitString( gensstring, ",", " " );
        nrgens:= Length( generators );

      fi;

      # Get the names of auxiliary generators needed.
      nraux:= Number( info.script,
                      line -> Length( line ) = 3 and IsInt( line[2] ) );
      if nrgens + nraux <= lalpha then
        auxnames:= alpha{ [ lalpha-nraux+1 .. lalpha ] };
        if not IsEmpty( Intersection( generators, auxnames ) ) then
          auxnames:= List( [ 1 .. nraux ],
                           i -> Concatenation( "X", String(i) ) );
        fi;
      else
        auxnames:= List( [ 1 .. nraux ],
                         i -> Concatenation( "X", String(i) ) );
      fi;
      nraux:= 1;

      # Initialize the result string.
      description:= "";

      # Scan the script linearly.
      script:= info.script;
      len:= Length( script );
      for i in [ 1 .. len ] do

        line:= script[i];

        if IsList( line[2] ) and IsString( line[2][1] ) then

          # condition line.
          word:= "";
          linelen:= Length( line[1] );
          for j in [ 1, 3 .. linelen-1 ] do
            Append( word, generators[ line[1][j] ] );
            if line[1][ j+1 ] = 2 then
              Append( word, generators[ line[1][j] ] );
            elif line[1][ j+1 ] <> 1 then
              Add( word, '^' );
              Append( word, String( line[1][ j+1 ] ) );
            fi;
          od;
          str:= ShallowCopy( line[2] );
          for j in [ 1 .. Length( str ) ] do
            if not IsBound( str[j] ) then
              str[j]:= word;
            fi;
          od;
          strline:= Concatenation( str );
          Add( strline, '=' );
          Append( strline, String( line[3] ) );

        elif Length( line ) = 2 then

          # definition line
          strline:= Concatenation( "|", generators[ line[1] ], "|=",
                        String( line[2] ) );

        elif Length( line ) = 3 and IsInt( line[2] ) then

          # definition line involving an auxiliary name
          strline:= Concatenation( "|", auxnames[ nraux ], "|=",
                        String( line[2] ), ", ", auxnames[ nraux ],
                        "^", String( line[3] ), "=", generators[ line[1] ] );
          nraux:= nraux+1;

        else

          # relation line
          linelen:= Length( line );
          if linelen = 3 then
            strline:= Concatenation( "|",
                          StringOfResultOfStraightLineProgram( line[2],
                              generators{ line[1] } ),
                          "|=", String( line[3] ) );
          else
            strline:= "|";
            for j in [ 1, 3 .. linelen-2 ] do
              Append( strline, generators[ line[j] ] );
              if line[ j+1 ] = 2 then
                Append( strline, generators[ line[j] ] );
              elif line[ j+1 ] <> 1 then
                Add( strline, '^' );
                Append( strline, String( line[ j+1 ] ) );
              fi;
            od;
            Append( strline, "|=" );
            Append( strline, String( line[ linelen ] ) );
          fi;

        fi;

        Append( description, strline );
        if i < len then
          Append( description, ", " );
        fi;

      od;

      # Store the value.
      info.description:= description;

    fi;

    # Return the result.
    return info.description;
end );


#############################################################################
##
#F  ScriptFromString( <string> )
##
InstallGlobalFunction( ScriptFromString, function( string )

    local gensnames,
          gensorder,
          lines,
          nrlines,
          k,
          line,
          pos,
          int,
          aux,
          len,
          pos2,
          script,
          nrgens,
          i,
          found,
          list,
          init,
          initlen,
          linelen,
          scr,
          try,
          j,
          word;

    gensnames:= [];
    gensorder:= [];
    lines:= SplitString( string, ",", " " );
    nrlines:= Length( lines );

    # Loop over the lines.
    script:= [];
    nrgens:= 0;
    k:= 1;
    while k <= nrlines do

      line:= lines[k];

      # The names of the standard generators occur in lines
      # starting not with `|' or lines containing neither `(' nor `^',
      # and having a letter at position $2$ and a non-letter at position $3$.
      if line[1] = '|' and IsAlphaChar( line[2] )
                       and not IsAlphaChar( line[3] )
                       and not ( '(' in line or '^' in line ) then

        # This entry belongs to a definition
        # (perhaps of an auxiliary element) via order.
        pos:= Position( line, '|', 1 );
        if pos = fail or line[ pos+1 ] <> '=' then
          return fail;
        fi;
        Add( gensnames, line{ [ 2 .. pos-1 ] } );
        int:= Int( line{ [ pos+2 .. Length( line ) ] } );
        if int = fail then
          return fail;
        fi;
        Add( gensorder, int );
        len:= Length( gensnames );
        nrgens:= nrgens + 1;

        # Check whether this was an auxiliary element,
        # and the next line (if there is one)
        # defines a generator relative to this one.
        if k < nrlines and lines[ k+1 ][1] <> '|'
                       and not '(' in lines[ k+1 ] then

          # This line belongs to a definition via a power.
          k:= k+1;
          line:= lines[k];
          pos:= Position( line, '^' );
          if pos = fail then
            return fail;
          fi;
          aux:= line{ [ 1 .. pos-1 ] };
          if gensnames[ len ] <> aux then
            return fail;
          fi;
          pos2:= Position( line, '=' );
          int:= Int( line{ [ pos+1 .. pos2-1 ] } );
          if int = fail then
            return fail;
          fi;
          gensnames[ len ]:= line{ [ pos2+1 .. Length( line ) ] };

          # Add the definition to the script.
          Add( script, [ nrgens, gensorder[ len ], int ] );

        else

          # Add the definition to the script.
          Add( script, [ nrgens, gensorder[ len ] ] );

        fi;

      else

        pos:= Position( line, '=' );
        if pos = fail then
          return fail;
        fi;
        int:= Int( line{ [ pos+1 .. Length( line ) ] } );
        if int = fail then
          return fail;
        fi;

        # Check whether the line matches the first part of a function string.
        found:= false;
        for i in [ 1, 3 .. Length( StandardGeneratorsFunctions )-1 ] do
          list:= StandardGeneratorsFunctions[ i+1 ];
          init:= list[1];
          initlen:= Length( init );
          if init[ initlen ] <> '(' then
            Error( "symbol <list> must enclose arguments in ( and )" );
          elif init = line{ [ 1 .. initlen ] } then

            # Find the word in question, and check it.
            pos2:= initlen + 1;
            linelen:= Length( line );
            while pos2 <= linelen and not line[ pos2 ] in "()" do
              pos2:= pos2 + 1;