Dear Joao, dear forum,
You can produce the elements of the free band with n generators using
the code at the end of this email: FreeBand(4), for example will
return the free band on 4 as lists of positive integers, i.e. the set
of all square free finite words over the alphabet "1", "2", "3", "4".
It takes about 2.5 seconds on my laptop to produce the elements of the
free band on 4 points. Since there are 2, 751,884,514, 765, elements
of the free band on 5 generators, it seems unlikely that these could
be produced in any reasonable amount of time.
The function U(set) below creates the list of all elements of the free
band containing the letters in set (where set is a list of positive
integers).
To represent any such list as word in "a", "b", "c", and "d" do:
gap> s:=FreeSemigroup("a", "b", "c", "d");
<free semigroup on the generators [ a, b, c, d ]>
gap> a:=s.1;; b:=s.2;; c:=s.3;; d:=s.4;;
gap> fb:=FreeBand(3);;
gap> EvaluateWord([a,b,c,d], Random(fb));
a*b*c*b*a*c
The code....
U:=function(P)
local out,u0, u1, w0, w1;
if Length(P)=1 then
return List(P, x-> [x]);
fi;
out:=[];
for u0 in P do
for w0 in U(Difference(P, [u0])) do
for u1 in P do
for w1 in U(Difference(P, [u1])) do
Add(out, Collapse(w0,u0,u1,w1));
od;
od;
od;
od;
return out;
end;
Collapse:=function(v0, u0, u1, v1)
local i, j;
w0:=Concatenation(v0, [u0]);
w1:=Concatenation([u1], v1);
i:=Length(w0);
while w0[i]<>u1 and i>1 do
i:=i-1;
od;
j:=0;
while j<=Length(w0)-i do
j:=j+1;
if w1[j]<>w0[i+j-1] then
return Concatenation(w0, w1);
fi;
od;
return Concatenation(w0, w1{[j+1..Length(w1)]});
end;
FreeBand:=function(n)
local out, enum, i;
out:=[];
enum:=EnumeratorOfCombinations([1..n]);
for i in [2..2^n] do
Append(out, U(enum[i]));
od;
return out;
end;
if not IsBound(EvaluateWord) then
EvaluateWord:=function ( gens, w )
local i, res;
if Length( w ) = 0 then
return gens[1] ^ 0;
fi;
res := gens[w[1]];
for i in [ 2 .. Length( w ) ] do
res := res * gens[w[i]];
od;
return res;
end;
fi;
>> From: Joao Araujo <mj...@classic.univ-ab.pt>
>> Subject: [GAP Forum] free bands
>> Date: 13 July 2009 11:56:13 GMT+01:00
>> To: fo...@gap-system.org
>>
>>
>> Dear all,
>>
>> I would be grateful if someone could tell me how I can use GAP to get all
>> the elements of the free band on 3 (or 4) generators.
>>
>> I thank in advance,
>> Joao
>>
>> _______________________________________________
>> Forum mailing list
>> Forum@mail.gap-system.org
>> http://mail.gap-system.org/mailman/listinfo/forum
>
>
> --
> Dr. Alexander Konovalov School of Computer Science
> & Centre for Interdisciplinary Research in Computational Algebra
> University of St Andrews Tel +44/0 (1334) 461633
> http://www.cs.st-andrews.ac.uk/~alexk Fax +44/0 (1334) 463278
> The University of St Andrews is a charity registered in Scotland:No.SC013532
>
>
>
>
>
>
>
--
James Mitchell
tinyurl.com/jdmitchell
The University of St Andrews is a charity registered in Scotland : No SC013532
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
