#############################################################################
##
## monom.gi GAP package IBNP Gareth Evans & Chris Wensley
##
#############################################################################
##
#M PrintNM( <mon> )
##
InstallMethod( PrintNM, "generic method for a noncommutative monomial",
true, [ IsList ], 0,
function( mon )
## Overview: Prints a monomial as a word
## Detail: this just calls a GBNP operation
##
if ( mon= [ ] ) then
Print( 1 );
else
Print( GBNP.TransWord( mon ) );
fi;
end );
InstallMethod( PrintNMList, "generic method for a list of monomials",
true, [ IsList ], 0,
function( L )
## Overview: Prints a list of monomials as a list of words
##
local mon;
if not ForAll( L, m -> IsList(m) ) then
Error( "expecting a list of monomials" );
fi;
for mon in L do
PrintNM( mon );
Print( "\n" );
od;
end );
#############################################################################
##
#M NM2GM( <list> <alg> )
##
InstallMethod( NM2GM, "generic method for a noncommutative monomial",
true, [ IsList, IsAlgebra ], 0,
function( mon, A )
## Overview: Converts a monomial from NM format
##
return NP2GP( [ [ mon ], [ 1 ] ], A );
end );
InstallMethod( GM2NM, "generic method for a noncommutative monomial",
true, [ IsAssociativeElement ], 0,
function( mon )
## Overview: Converts a monomial to NM format
##
return GP2NP( mon )[1][1];
end );
InstallMethod( NM2GMList, "for a list of noncommutative monomials",
true, [ IsList, IsAlgebra ], 0,
function( L, A )
## Overview: Converts a list of monomial from NM format
##
return List( L, m -> NP2GP( [ [ m ], [ 1 ] ], A ) );
end );
InstallMethod( GM2NMList, "for a list of noncommutative monomials",
true, [ IsList ], 0,
function( L )
## Overview: Converts a monomial to NM format
##
return List( L, m -> GP2NP( m )[1][1] );
end );
#############################################################################
##
#M SuffixNM( <pol> <int> )
#M SubwordNM( <pol> <int> <int> )
#M PrefixNM( <pol> <int> )
##
InstallMethod( SuffixNM, "generic method for a monomial and a length",
true, [ IsList, IsInt ], 0,
function( mon, i )
local len, j;
if ( i=0 ) then
return [ ];
elif ( i < 0 ) then
return fail;
fi;
len := Length( mon );
j := Minimum( i, len );
return mon{[len-j+1..len]};
end );
InstallMethod( SubwordNM, "generic method for monomial, start and finish",
true, [ IsList, IsPosInt, IsPosInt ], 0,
function( mon, s, f )
local len, i, j;
if ( s > f ) then
Error( "start cannot be greater than finish" );
fi;
len := Length( mon );
i := Minimum( s, len );
j := Minimum( f, len );
return mon{[i..j]};
end );
InstallMethod( PrefixNM, "generic method for a monomial and a length",
true, [ IsList, IsInt ], 0,
function( mon, i )
local len, j;
if ( i=0 ) then
return [ ];
elif ( i<0 ) then
return fail;
fi;
len := Length( mon );
j := Minimum( i, len );
return mon{[1..j]};
end );
#############################################################################
##
#M SubwordPosNM( <mon>, <mon>, <posint>, <posint> )
#M IsSubwordNM( <mon>, <mon> )
#M SuffixPrefixPosNM( <mon>, <mon>, <posint>, <posint> )
##
InstallMethod( SubwordPosNM,
"generic method for 2 monomials and a start position",
true, [ IsList, IsList, IsPosInt ], 0,
function( small, large, start )
## Overview: Is the 1st arg a subword of the 2nd arg?
## if so, return start pos in 2nd arg
## Detail: Answers the question "Is small a subword of large?"
## The function returns i if small is a subword of large,
## where i is the position in large of the first subword found,
## and returns 0 if no overlap exists.
## We start looking for subwords starting at position start in large
## and finish looking for subwords when all possibilities have been
## exhausted (we work left-to-right).
## To test all possibilities the 3rd argument should be 1,
## but note that you should use the function (IsSubword)
## if you only want to know if a monomial is a subword of another
## monomial and are not fussed where the overlap takes place.
local i, slen, llen;
i := start;
slen := Length( small );
llen := Length( large );
## while there are more subwords to test for
while ( i <= llen-slen+1 ) do
## if small is equal to a subword of large
if ( small = large{[i..i+slen-1]} ) then
return i; ## subword found
fi;
i := i+1;
od;
return 0; ## no subwords found
end );
InstallMethod( IsSubwordNM,
"generic method for 2 monomials",
true, [ IsList, IsList ], 0,
function( small, large )
## Overview: Does small appear as a subword in large?
local i, lens, lenl;
lens := Length( small );
lenl := Length( large );
for i in [1..lenl-lens+1] do
if ( small = large{[i..i+lens-1]} ) then
return true; ## overlap found
fi;
od;
return false; ## no overlap found
end );
InstallMethod( SuffixPrefixPosNM,
"generic method for 2 monomials and a start position",
true, [ IsList, IsList, IsPosInt, IsInt ], 0,
function( left, right, start, limit )
## Overview: Returns size of smallest overlap of type
## (suffix of 1st arg = prefix of 2nd arg)
## Detail: Answers the question "Is a suffix of left a prefix of right?"
## The function returns i if a suffix of left equals a prefix of right,
## where i is the length of the smallest overlap,
## and returns 0 if no overlap exists.
## The lengths of the overlaps looked at are controlled by the
## 3rd and 4th arguments - start by looking at the overlap of size
## start and finish by looking at the overlap of size limit.
## It is the user's responsibility to ensure that these bounds are
## correct - no checks are made by the function.
## To test all possibilities, the 3rd argument should be 1
## and the fourth argument should be min( |left|, |right| ) - 1.
local i;
i := start;
while ( i <= limit ) do ## for each overlap
if ( SuffixNM( left, i ) = PrefixNM( right, i ) ) then
return i; ## prefix found
fi;
i := i+1;
od;
return 0; ## no prefixes found
end );
#############################################################################
##
#M LeadVarNM( <mon> )
#M LeadExpNM( <mon> )
#M TailNM( <mon> )
##
InstallMethod( LeadVarNM, "generic method for a monomial",
true, [ IsList ], 0,
function( mon )
if ( mon = [ ] ) then
Error( "empty monomial" );
fi;
return mon[1];
end );
InstallMethod( LeadExpNM, "generic method for a monomial",
true, [ IsList ], 0,
function( mon )
local x, done, len, j, count;
x := LeadVarNM( mon );
done := false;
len := Length( mon );
j := 1;
count := 1;
while ( j < len ) and ( not done ) do
j := j+1;
if ( mon[j] = x ) then
count := count + 1;
else
done := true;
fi;
od;
return count;
end );
InstallMethod( TailNM, "generic method for a monomial",
true, [ IsList ], 0,
function( mon )
return mon{ [LeadExpNM(mon)+1..Length(mon)] };
end );
############################################################################
##
#M DivNM( <mon> <mon> )
##
## Overview: Returns all possible ways that 2nd arg divides 1st arg;
## 3rd arg = is division possible?
## Detail: Given two NMs _m_ and _d_, this function returns all possible
## ways that _d_ divides _m_ in the form of an FMonPairList.
## For example, if m = abcababc and d = ab, then the output FMonPairList
## is ((abcab, c), (abc, abc), (1, cababc))..
## External variables needed: int pl;
InstallMethod( DivNM, "for two monomials", true, [ IsList, IsList ], 0,
function( m, d )
local i, lenm, lend, diff, resm, resp, pair;
resm := [ ]; ## initialise the output list
lenm := Length( m );
lend := Length( d );
if ( lenm < lend ) then ## no possible divisions if |m| < |d|
return [ ];
fi;
## we must now consider each possibility in turn
diff := lenm - lend;
for i in Reversed( [1..diff+1] ) do ## working right to left
## is the subword of m of length |d| starting at i equal to d?
if ( d = m{[i..i+lend-1]} ) then
## match found; push the left/right factors onto the output list
pair := [ PrefixNM( m, i-1 ),
SuffixNM( m, lenm-lend-i+1 ) ];
Add( resm, pair );
if ( InfoLevel( InfoIBNP ) > 2 ) then
PrintNMList( pair );
fi;
fi;
od;
resp := List( resm, L -> [ L, [1,1] ] );
return resm;
end);
#############################################################################
##
#E monom.gi . . . . . . . . . . . . . . . . . . . . . . . . . . . ends here
##
