[GAP Forum] Cyclically Reduced Words

[Alexander Hulpke]

Dear GAP-Forum,


On Mar 27, 2006, at 8:48 AM, pjd at maths.gla.ac.uk wrote:

>
> Given the alphabet {a,a^-1,b,b^-1}, how can I get GAP to produce a  
> list of
> cyclically reduced words of length at most 3, 4, etc?

There is no predefined function which does this. What I would do if I  
had to construct these words is to take the code for `Tuples' (in lib/ 
combinat.gi) to construct combinations of [-n,-(n-1),- 
(n-2)..-2,-1,1,2,3,..n] and modify it to not permit i following -i  
and vice versa or have a word starting in i and ending in -i and vice  
versa.

If your application is not time/memory critical the following naive  
approach is likely the easiest:

f:=FreeGroup("a","b");
IsCycRed:=l->l[1]<>-l[Length(l)] and ForAll([1..Length(l)-1],j->l[j] 
<>-l[j+1]);
len:=4; # or whatever
w:=Filtered(Tuples([-2,-1,1,2],len),IsCycRed);

fam:=FamilyObj(One(f));;
List(w,i->AssocWordByLetterRep(fam,i));

Best,

     Alexander Hulpke