I cc: this to sage-combinat-devel, as there more people who do this kind of
stuff hang on a regular basis.
On Thursday, 2 February 2012 07:40:07 UTC+8, Matthieu Deneufchâtel wrote:
>
> I tried to remove all the french expressions in my code.
>
>
> ########## Lyndon words ######################
> import sage.combinat.lyndon_word as LW
>
> ########## Shuffle product ######################
> from sage.combinat.words.shuffle_product import ShuffleProduct_w1w2 as
> SP
>
> ########## Combinatorial Free Module structure ######################
> from sage.combinat.free_module import CombinatorialFreeModule as CFM
>
> ########## Free algebra over 2 generators a and b
> ######################
> R.<a,b>=FreeAlgebra(QQ,2)
>
> Module=CombinatorialFreeModule(QQ,R)
>
>
> ######################################################################
> ############ Module Structure for k<a,b> \otimes k<a,b> ##############
> ######################################################################
>
> ########## Tensor product k<a,b> \otimes k<a,b> ######################
> def TP_free_algebra(w1,w2):
> if type(w1)==Integer:
> if type(w2)==Integer:
> return w1*w2*tensor((Module.basis()[1],Module.basis()[1]))
> else:
> L2=list(w2)
> result=0
> for i in L2:
> result+=w1*i[0]*tensor((Module.basis()[1],Module.basis()[i[1]]))
> return result
> else:
> if type(w2)==Integer:
> L1=list(w1)
> result=0
> for i in L1:
> result+=w2*i[0]*tensor((Module.basis()[i[1]],Module.basis()[1]))
> return result
> else:
> L1=list(w1)
> L2=list(w2)
> result=0
> # print(L1,L2)
> for i in L1:
> for j in L2:
> result+=i[0]*j[0]*tensor((Module.basis()[i[1]],Module.basis()
> [j[1]]))
> return result
>
> ### Tests ###
> TP_free_algebra(1,1)
> TP_free_algebra(1,a*b)
> TP_free_algebra(a*b,1)
> TP_free_algebra(a,a*b*a)
>
> ########## Product in k<a,b> \otimes k<a,b> ######################
> def prod_TP(t1,t2):
> result=0
> L1=list(t1)
> L2=list(t2)
> for i in L1:
> for j in L2:
> result+=i[1]*j[1]*TP_free_algebra(R(i[0][0])*R(j[0][0]),R(i[0]
> [1])*R(j[0][1]))
> return result
>
> ### Tests ###
> prod_TP(TP_free_algebra(a,a),TP_free_algebra(b,b))
> prod_TP(tensor((Module.basis()[1],Module.basis()
> [1])),TP_free_algebra(b,b))
> prod_TP(TP_free_algebra(a^2*b*a^2,a),TP_free_algebra(b,b^2))
>
> ##################################################################################
>
>
> ###### Morphisms between \left\{ a , b \right\}^* \leftrightarrow
> k<a,b> ########
> ##################################################################################
>
>
>
> ########## Morphism \left\{ a , b \right\}^* \rightarrow k<a,b>
> ##################
> def toA(w):
> if len(w)==0:
> return 1
> if len(w)==1:
> return eval(eval('w[0]'))
> else:
> return eval(eval('w[0]'))*toA(w[1:w.length()])
>
> ### Tests ###
> toA(Word(''))
> toA(Word('abb'))
>
> ########## Morphism k<a,b> \rightarrow \left\{ a , b \right\}^*
> #################
> def toWord(FAelem):
> if type(FAelem)==Integer:
> return Word('')
> else:
> if
> type(FAelem)==sage.algebras.free_algebra_element.FreeAlgebraElement:
> temp=list(list(FAelem)[0][1])
> elif
> type(FAelem)==sage.monoids.free_monoid_element.FreeMonoidElement:
> temp=list(FAelem)
> result=Word('')
> for i in temp:
> for j in range(i[1]):
> result=result*Word(str(i[0]))
> return result
>
> ### Tests ###
> toWord(1)
> toWord(a*b*b*a*b)
> toWord(R(a*b*b*a*b))
> S=a*b*a*b+b*a
> type(list(S)[0][1])
> toWord(list(S)[0][1])
>
> ##################################################################################
>
>
> ############################### Scalar Products
> #################################
> ##################################################################################
>
>
>
> ########## \langle S | w \rangle ######################
> def ScalProd(S,w):
> v=toA(w)
> if type(S)==Integer:
> if w==Word(''):
> return S
> else:
> return 0
> else:
> l=list(S)
> dic=dict()
> for (c,m) in l:
> dic[R(m)]=c
> # print(dic)
> if dic.has_key(toA(w))==True:
> return dic[v]
> elif w==Word('') and type(list(S)[0][1])==Integer:
> return list(S)[0][0]
> elif w==Word('') and type(list(S)[0]
> [1])==sage.monoids.free_monoid_element.FreeMonoidElement and
> len(list(S)[0][1])==0:
> return list(S)[0][0]
> else:
> return 0
>
> ### Tests ###
> ScalProd(2+a*b+36*a,Word('aaaaa'))
> ScalProd(2+a*b+a,Word(''))
> ScalProd(2+a*b+36*a,Word('a'))
>
> ########## \langle S | T \rangle ######################
> def SPSeries(S,T):
> sp=0
> if type(S)==Integer:
> if type(T)==Integer:
> return S*T
> else:
> L2=list(T)
> if type(L2[0][1])==Integer:
> return S*L2[0][0]
> else:
> return sp
> else:
> if type(T)==Integer:
> #L1=list(S)
> #if type(L1[0][1])==Integer:
> return T*ScalProd(S,Word(''))
> else:
> L1=list(S)
> L2=list(T)
> dic1=dict()
> dic2=dict()
> for (c,m) in L1:
> dic1[m]=c
> for (c,m) in L2:
> dic2[m]=c
> l1=dic1.keys()
> l2=dic2.keys()
> # print(dic1,dic2)
> L=[i for i in l1+[j for j in l2 if j not in l1]]
> # print(L)
> for i in L:
> if dic1.has_key(i)==True:
> if dic2.has_key(i)==True:
> sp+=dic1[i]*dic2[i]
> return sp
>
> ### Tests ###
> SPSeries(2+a*b+36*a,1)
> SPSeries(2+a*b+36*a,2*a)
>
> ##################################################################################
>
>
> ###### Bialgebra structure of k<a,b> ########
> ##################################################################################
>
>
>
> ########## Coproduct associated to the shuffle product
> ######################
> def Delta(w):
> result=0
>
> if type(w)==sage.combinat.words.word.FiniteWord_str or
> type(w)==sage.combinat.words.word.FiniteWord_list:
> if w.length()==1:
> return tensor((Module.basis()[toA(w)],Module.basis()
> [toA(Word(''))]))+tensor((Module.basis()[toA(Word(''))],Module.basis()
> [toA(w)]))
> else:
> # print(w[0],w[1:w.length()])
> return prod_TP(Delta(Word(w[0])),Delta(w[1:w.length()]))
>
> elif type(w)==sage.algebras.free_algebra_element.FreeAlgebraElement:
> if w==a or w==b:
> return tensor((Module.basis()[w],Module.basis()[toA(Word(''))]))
> +tensor((Module.basis()[toA(Word(''))],Module.basis()[w]))
> else:
> for i in list(w):
> # print(i[1],type(i[1]))
> result+=i[0]*Delta(toWord(i[1]))
> return result
>
> ### Tests ###
> Delta(Word('a'))
> Delta(Word('b'))
> Delta(Word('ab'))
>
> ########## Counit ######################
> def epsilon(S):
> return ScalProd(S,Word(''))
>
> ### Tests ###
> epsilon(2+a*b+a)
> epsilon(2*a+a*b+a)
>
> ##################################################################################
>
>
> ################################ Bases of k<a,b>
> ################################
> ##################################################################################
>
>
>
> ########## Transforms the standard bracketing into the corresponding
> series of k<a,b> ##############
> def expbrack(l):
> if len(l)==1:
> return eval(l)
> if len(l[0])==1:
> if len(l[1])==1:
> s=eval(l[0])
> t=eval(l[1])
> return s*t-t*s
> else:
> s=eval(l[0])
> t=expbrack(l[1])
> return s*t-t*s
> else:
> if len(l[1])==1:
> s=expbrack(l[0])
> t=eval(l[1])
> return s*t-t*s
> else:
> s=expbrack(l[0])
> t=expbrack(l[1])
> return s*t-t*s
>
> ########## Poincar\'é-Birkhoff-Witt basis of k<a,b>
> ######################
> def PBW(w):
> if w.length()==0:
> return 1
> elif w.length()==1:
> return eval(eval('w[0]'))
> else:
> if w.is_lyndon()==True:
> # print(LW.standard_bracketing(w),w)
> return expbrack(LW.standard_bracketing(w))
> else:
> lf=w.lyndon_factorization()
> # print(lf)
> # sb=map(LW.standard_bracketing,lf)
> # sr=map(expbrack,sb)
> listresult=map(PBW,lf)
> # print(listresult)
> return prod(i for i in listresult)
>
> ########## List of words whose shuffle product gives w
> ######################
> def InvShuff(w):
> z=w.length()
> L=[]
> for i in range(0,z+1):
> L1=Words('ab',i)
> L2=Words('ab',z-i)
> for w1 in L1:
> for w2 in L2:
> l=SP(w1,w2).list()
> # if w in l:
> for j in l:
> if j==w:
> L.append((w1,w2))
> return L
>
> ########## Coefficient of w in the shuffle product of S and T
> ######################
> def ShuffSeriesCoeff(S,T,w):
> L=InvShuff(w)
> result=0
> # print L
> for couple in L:
> coeff1=ScalProd(S,couple[0])
> # print(couple[0],coeff1)
> coeff2=ScalProd(T,couple[1])
> # print(couple[1],coeff2)
> result+=coeff1*coeff2
> return result
>
> ########## Shuffle product of two series ######################
> def ShuffSeries(S,T):
> dic1=dict()
> dic2=dict()
> result=0
>
> if type(S)==Integer:
> dic1[1]=S
> else:
> l1=list(S)
> for (c,m) in l1:
> dic1[m]=c
>
> if type(T)==Integer:
> dic2[1]=T
> else:
> l2=list(T)
> for (c,m) in l2:
> dic2[m]=c
>
> L1=dic1.keys()
> L2=dic2.keys()
>
> if type(L1[0])==Integer and len(L1)==1:
> if type(L2[0])==Integer and len(L2)==1:
> z=0
> else:
> z=max(map(len,L2))
> else:
> if type(L2[0])==Integer and len(L2)==1:
> z=max(map(len,L1))
> else:
> l1=max(map(len,L1))
> l2=max(map(len,L2))
> z=l1+l2
> # print(z)
>
> M=[i for j in range(1,z+1) for i in Words('ab',j)]
> # print(M)
> result+=ScalProd(S,Word(''))*ScalProd(T,Word(''))
> for w in M:
> temp=list(Delta(w))
> # print(temp)
> for i in temp:
> # print(w,i)
> result+=i[1]*ScalProd(S,toWord(i[0][0]))*ScalProd(T,toWord(i[0]
> [1]))*toA(w)
>
> return result
>
> ########## Shuffle powers of a series ######################
> def PowerShuff(S,k):
> if k==0:
> return 1
> else:
> return ShuffSeries(S,PowerShuff(S,k-1))
>
> ########## Transforms a factorization into the shuffle product of its
> elements ######################
> def listtoShuff(sf):
> if len(sf)==1:
> return sf[0]
> else:
> return ShuffSeries(sf[0],listtoShuff(sf[1:len(sf)]))
>
> ########## Basis dual to the PBW Basis ######################
> def Sbasis(w):
> if len(w)==0:
> return 1
> elif len(w)==1:
> return toA(w)
> else:
> if w.is_lyndon()==True:
> firstletter=eval(eval('w[0]'))
> l=len(w)
> m=Word(w[1:l])
> u=Sbasis(m)
> return firstletter*u
> else:
> lf=w.lyndon_factorization()
> multiplicities=[]
> multiplicities.append(1)
> temp=lf[0]
> j=0
> for i in range(1,len(lf)):
> if lf[i]==temp:
> multiplicities[j]+=1
> else:
> j+=1
> temp=lf[i]
> multiplicities.append(1)
> prod=1
> for i in multiplicities:
> prod*=factorial(i)
> # print(prod)
> slf=map(Sbasis,lf)
> # print(slf)
> return 1/prod*listtoShuff(slf)
>
> ### Tests (Duality of P_w and S_w : \langle P_u | S_v \rangle =
> \delta_{uv}) ###
> for i in [w for j in range(1,5) for w in Words('ab',j)]:
> for j in [w for j in range(1,5) for w in Words('ab',j)]:
> print(i==j,SPSeries(PBW(i),Sbasis(j)))
>
> ########## Basis obtained for the "pure" Lyndon words
> ######################
> def Sbasistilde(w):
> if len(w)==0:
> return 1
> elif w.is_lyndon()==True:
> return toA(w)
> else:
> lf=w.lyndon_factorization()
> multiplicities=[]
> multiplicities.append(1)
> temp=lf[0]
> j=0
> for i in range(1,len(lf)):
> if lf[i]==temp:
> multiplicities[j]+=1
> else:
> j+=1
> temp=lf[i]
> multiplicities.append(1)
> prod=1
> for i in multiplicities:
> prod*=factorial(i)
> # print(prod)
> slf=map(Sbasistilde,lf)
> # print(slf)
> return 1/prod*listtoShuff(slf)
>
> ##################################################################################
>
>
> ########### Coefficients of the expansion of a series on a basis
> ################
> ##################################################################################
>
>
>
> ############ List of the coefficients of a series on the Lie Monomial
> ############
> def devP(S,L):
> if S!=0:
> support=[toWord(i[1]) for i in list(S)]
> j=2
> temp=support[len(support)-1]
> while temp.is_lyndon()==False and j<=len(support):
> temp=support[len(support)-j]
> j+=1
> # print(temp)
> coeff=SPSeries(S,toA(temp))
> # print(coeff)
> L.append((temp,coeff))
> Pol=PBW(temp)
> # print(temp.is_lyndon(),Pol)
> remainder=S-coeff*Pol
> return devS(remainder,L)
> else:
> #print(sum(i[1]*PBW(i[0]) for i in L)==S)
> return L
>
> ### Développement sur les S^{'}_\ell, \ell \in {\rm Lyn}(a,b)
> (Reutenauer) par "division euclidienne" ###
> def devS(S,L):
> if S!=0:
> support=[toWord(i[1]) for i in list(S)]
> if len(support)>1:
> # print(support)
> min=support[0]
> for w in support:
> if min.lex_less(w):
> min=w
> # for j in range(1,len(support)-1):
> # if min.lex_less(support[j+1])==True:
> # print j
> # min=support[j+1]
> # print(min)
> coeff=SPSeries(S,toA(min))
> # print(coeff)
> L.append((min,coeff))
> Pol=Sbasistilde(min)
> # print(temp.is_lyndon(),Pol)
> remainder=S-coeff*Pol
> return devS(remainder,L)
> else:
> temp=support[len(support)-1]
> coeff=SPSeries(S,toA(temp))
> L.append((temp,coeff))
> Pol=Sbasistilde(temp)
> remainder=S-coeff*Pol
> return devS(remainder,L)
> else:
> #print(sum(i[1]*PBW(i[0]) for i in L)==S)
> return L
>
> ##################################################################################
>
>
> ################ Test of the primitive character of a series
> ####################
> ##################################################################################
>
>
>
> def is_primitive(S):
> result=0
> # print(list(Delta(S)))
> # print(list(TP_free_algebra(S,1)+TP_free_algebra(1,S)))
> L1=list(Delta(S))
> L2=list(TP_free_algebra(S,1)+TP_free_algebra(1,S))
> for i in L1:
> for j in L2:
> if i[0]==j[0]:
> result+=i[1]-j[1]
> return result==0
>
> ### Tests ###
> for i in [w for j in range(1,6) for w in Words('ab',j) if
> w.is_lyndon()==True]:
> print(is_primitive(PBW(i)))
>
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/sage-combinat-devel/-/3PGiXp4xZ4kJ.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
