devoir1_2.sagews

def longueur(U,V):
    C=[]
    for i in range(len(U)+1):
        C.append([])
        for j in range(len(V)+1):
            C[i].append([0,""])
    for i in range(len(U)):
        C[i+1][0]=[i+1,"u"]
    for j in range(len(V)):
        C[0][j+1]=[j+1,"l"]
        for i in range(len(U)):
            if U[i]==V[j]:
                C[i+1][j+1][0]=C[i][j][0]+1
                C[i+1][j+1][1]="ul"
            else:
                C[i+1][j+1][0]=min (C[i][j+1][0],C[i+1][j][0])+1
                if C[i+1][j+1][0]== C[i][j+1][0]+1:
                    C[i+1][j+1][1]="u"
                else:
                    C[i+1][j+1][1]="l"
    return C
def matriz_num(C):
    return [[C[i][j][0] for j in range (len(C[i]))] for i in range(len(C))]
def matriz_dir(C):
    return [[C[i][j][1] for j in range (len(C[i]))] for i in range(len(C))]

def palabra(V,U,C,D):
    pal=""
    l=D[-1][-1]
    pos_U=len(U)
    pos_V=len(V)
    while l!=0:
        print l,C[pos_U][pos_V],
        if C[pos_U][pos_V]=='l':
            pal=V[pos_V-1]+pal
            pos_V=pos_V-1
        elif C[pos_U][pos_V]=='u':
            pal=U[pos_U-1]+pal
            pos_U=pos_U-1
        else: #C[pos_U][pos_V]=='ul':
            pal=V[pos_V-1]+pal
            pos_V=pos_V-1
            pos_U=pos_U-1
        print pal
        l=l-1
    return pal

U="fourniture"
V="informatique"
matriz=longueur(U,V)
NUM=matriz_num(matriz)
DIR=matriz_dir(matriz)

for i in range(len(NUM)):
    for j in range(len(NUM[i])):
        print  NUM[i][j],
    print

0 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 3 4 5 6 7 8 9 10 11 12 2 3 4 4 4 5 6 7 8 9 10 11 12 3 4 5 5 5 6 7 8 9 10 11 11 12 4 5 6 6 6 6 7 8 9 10 11 12 13 5 6 6 7 7 7 8 9 10 11 12 13 14 6 6 7 8 8 8 9 10 11 11 12 13 14 7 7 8 9 9 9 10 11 11 12 13 14 15 8 8 9 10 10 10 11 12 12 13 14 14 15 9 9 10 11 11 11 12 13 13 14 15 15 16 10 10 11 12 12 12 13 14 14 15 16 16 16

palabra(V,U,DIR,NUM)

16 ul e 15 u re 14 ul ure 13 u ture 12 l qture 11 ul iqture 10 u niqture 9 l tniqture 8 l atniqture 7 l matniqture 6 ul rmatniqture 5 u urmatniqture 4 ul ourmatniqture 3 ul fourmatniqture 2 l nfourmatniqture 1 l infourmatniqture 'infourmatniqture'

import random
alphabet="asdf"
def tabla_mul (alphabet):
    tab=[]
    for x in alphabet:
        tab.append ([random.choice(alphabet) for x in range(len(alphabet))])
    return tab

Multip=tabla_mul (alphabet)
alphabet, Multip

('asdf', [['d', 'f', 'f', 's'], ['d', 'a', 'a', 'a'], ['s', 'd', 'd', 'd'], ['a', 'a', 'f', 'a']])

def pal_azar(alphabet,n):
    pal=""
    for i in range(n):
        pal=pal+random.choice(alphabet)
    return pal

palabra=pal_azar(alphabet,5)
letra=random.choice(alphabet)

def multiplicar(a,b,tabla,alphabet):
    return tabla[alphabet.index(a)][alphabet.index(b)]
def prod_posibles (A,B,tabla,alphabet):
    conj=set([])
    for a in A:
        for b in B:
            conj.add(multiplicar(a,b,tabla,alphabet))
    return conj

def parentesis(alphabet,tabla,palabra,letra):
    C=[]
    for i in range(len(palabra)):
        C.append([])
        for j in range(len(palabra)):
            C[i].append(set([]))
    for i in range(len(palabra)):
        C[i][i]=set(palabra[i])
    for d in range(1,len(palabra)):
        for t in range(len(palabra)-d):
            i=t
            j=t+d
            for k in range(i+1,j+1):
                prod=prod_posibles(C[i][k-1], C[k][j],tabla,alphabet)
                C[i][j]=C[i][j].union(prod)
            print i,j ,C[i][j]     

    return letra in C[0][-1]

def prod_posibles_comp (A,B,tabla,alphabet,it=1):
    conj=[]
    aux=set([])
    for i in range(len (A)):
        a0=A[i][0]
        for j in range(len (B)):
            b0=B[j][0]
            temp= multiplicar(a0,b0,tabla,alphabet)
            if temp not in aux:
                aux.add(temp)
                conj=conj+[[temp,a0,b0,it]]
    return conj,aux

def parentesis_comp(alphabet,tabla,palabra,letra):
    C=[]
    aux=[]
    for i in range(len(palabra)):
        C.append([])
        aux.append([])
        for j in range(len(palabra)):
            C[i].append([])
            aux[i].append(set([]))
    for i in range(len(palabra)):
        C[i][i]=[[palabra[i],"",palabra[i],0]]
        aux[i][i]=set(palabra[i])
#        print C[i][i][0]
    for d in range(1,len(palabra)):
        for t in range(len(palabra)-d):
            i=t
            j=t+d
            for k in range(i+1,j+1):
                prod=prod_posibles_comp(C[i][k-1], C[k][j],tabla,alphabet,k)
                C[i][j]=C[i][j]+[tupla for tupla in prod[0] if tupla[0] not in aux[i][j]]
                aux[i][j]=aux[i][j].union(prod[1])
                 
#            print i,j ,C[i][j]     
    print C[0][-1]
    return letra in aux[0][-1],C

solucion=parentesis_comp(alphabet,Multip,palabra,letra)
solucion[1][0][-1]

[['a', 'f', 's', 1], ['f', 'f', 'd', 1], ['s', 'a', 'f', 2], ['d', 'd', 's', 3]] [['a', 'f', 's', 1], ['f', 'f', 'd', 1], ['s', 'a', 'f', 2], ['d', 'd', 's', 3]]

def construir_parentesis(letra,palabra,tabla,ini=0,fin=len(palabra)-1):
    if fin==ini:
        print "(",palabra[ini],")",
    elif fin==ini+1:
        print "(",palabra[ini],palabra[fin],")",
    else:
        x=[tupla for tupla in tabla[ini][fin] if tupla[0]==letra][0]
        mid=x[3]-1
#        print (mid-ini+1)*"x",(fin-mid)*"y"
#        print [palabra[j] for j in range(ini,mid+1)],
#        print [palabra[j] for j in range(mid+1,fin+1)]
#        print "(",construir_parentesis(x[1],palabra,tabla,ini,x[3]-1),")","(",construir_parentesis(x[2],palabra,tabla,x[3],fin),")","=",letra
#        print "len (",x[1],")=",mid-ini+1
#        print construir_parentesis(x[1],palabra,tabla,ini,mid)
#        print "len (",x[2],")=",fin-mid
#        print construir_parentesis(x[2],palabra,tabla,mid+1,fin)
#        print "..........."
        print "(",construir_parentesis(x[1],palabra,tabla,ini,mid),construir_parentesis(x[2],palabra,tabla,mid+1,fin),")",
        

construir_parentesis(letra,palabra,solucion[1])

( ( f ) None ( ( a a ) None ( a f ) None ) None )

def parentesis_comp(alphabet,tabla,palabra,letra):
    C=[]
    aux=[]
    for i in range(len(palabra)):
        C.append([])
        aux.append([])
        for j in range(len(palabra)):
            C[i].append([])
            aux[i].append(set([]))
    for i in range(len(palabra)):
        C[i][i]=[[palabra[i],"",palabra[i],0]]
        aux[i][i]=set(palabra[i])
    for d in range(1,len(palabra)):
        for t in range(len(palabra)-d):
            i=t
            j=t+d
            for k in range(i+1,j+1):
                prod=prod_posibles_comp(C[i][k-1], C[k][j],tabla,alphabet,k)
                C[i][j]=C[i][j]+[tupla for tupla in prod[0] if tupla[0] not in aux[i][j]]
                aux[i][j]=aux[i][j].union(prod[1])
    return letra in aux[0][-1],C

solucion=parentesis_comp(alphabet,Multip,palabra,letra)
solucion[1][0][-1]

[['a', 'f', 's', 1], ['f', 'f', 'd', 1], ['s', 'a', 'f', 2], ['d', 'd', 's', 3]] [['a', 'f', 's', 1], ['f', 'f', 'd', 1], ['s', 'a', 'f', 2], ['d', 'd', 's', 3]]

def construir_parentesis(letra,palabra,tabla,ini=0,fin=len(palabra)-1):
    if fin==ini:
        print "(",palabra[ini],")",
    elif fin==ini+1:
        print "(",palabra[ini],palabra[fin],")",
    else:
        x=[tupla for tupla in tabla[ini][fin] if tupla[0]==letra][0]
        mid=x[3]-1
        print "(",construir_parentesis(x[1],palabra,tabla,ini,mid),construir_parentesis(x[2],palabra,tabla,mid+1,fin),")",
    return ""
        

construir_parentesis(letra,palabra,solucion[1])

( ( f ) ( ( a a ) ( a f ) ) ) ''