#######################################Exercice 1############

## what we return in output is a list
def double_list(l):
    ## take the length
    n=len(l)
    ## initialize the empty list
    output=[]
    for i in range(0,n):
        ## we take the ith element and multiply by two and add it to the list output
        output.append(2*l[i])
    return output    


print(double_list([1,5,9,50]))


#############################Exercice 2 ######################

### 2a

#We call our function scalar(v1,v2)
# that takes two lists v1 v2 of n elements and computes the scalar product
#
def scalar(v1,v2):
    ## initialize the output to 0
    output=0
    if (len(v1)!=len(v2)):
        print("Error")
        return -1
    ## size of the vector is n
    n=len(v1)    
    for i in range(0, n):
        output+= v1[i]*v2[i]
    return output
            
print(scalar([1,1],[-1,1]))
## 2b
### we call our function product_matrix_vector(mat,vect)
### mat is a ntimes n matrix and vect is a n vector columm

def product_matrix_vector (mat,vect):
    if (len(n)!= len(mat)):
        print ("Error")
        return -1
    n=len(vect)
    output=list(range(0,n))
    for i in range(0,n):
        ## initialize the value of the i-th output row to 0
        output[i]=0
        ## apply the formula, the colum i is a sum on k
        for k in range(0,n):
            output[i]+= mat[i][k]* vect[k]        
    return output






######################################################
#####################Exercice 3 #####################
###################################################
from string import *

def convert_char(c):
    return ascii_lowercase.find(c,0)

def convert_text(t):
    n=len(t)
    output=[]
    for i in range(0,n):
        output.append(convert_char(t[i]))
    return output
    
print(convert_text("jesuisunenouvelleplanete"))    


print(convert_text("abcdefghijklmnopqrstu"))    


############### question b

#########a permutation is a list of size n containing 0,1,...,n-1
#### our function is decompose (l)  where l is a permutation
#### in output, we give a list of transposition, which is viewed as a list of 2 numbers. 
#### [ [1,2], [1,4]] would correspond to the transposition (1,2) composed with (1,4)

##we first call our function composition
def composition(list1,list2):
    if (len(list1)!= len(list2)):
        print("Error")
        return -1
    n=len(list1)    
    ### initialize the identity map
    output= list(range(0,n))
    for i in range(0,n):
        ## we compute the i-th element
        output[i]=list1[list2[i]]    
        #print(output)
    return output
    

### we define the transposition between a and b in a permutation of n elements (a,b are smaller than n-1)
### returns a list with n elements
def transposition(a,b,n):
    output=list(range(0,n))
    output[a]=b
    output[b]=a
    return output

### recursive function for the decomposition, note that it gives the empty list if l is the identity

### output list of pairs [[1,2], [2,3], [3,0] ]
def rec_decomposition(l, k):
    if (k >= (len(l)-1)):
        ## we are done here
        return []
    ### k is not len(l-1)
    ### we now check whether k is fixed.
    if (l[k]==k):
        return rec_decomposition (l,k+1)
    else:
        b=l[k]
        n=len(l)
        t_kb=transposition(k,b,n)
        ## we decompose t_kb composed with l
        output=rec_decomposition(composition(t_kb, l), k+1)
        ### we add the transposition k b in our output list
        output.insert(0,[k,b])
        return output

### decomposition prints the decomposition of the permutation and returns the corresponding list of transposition.
def decomposition(l):   
    dec_list=rec_decomposition(l,0)
    chain="The permutation " +str(l) +  "   can be decomposed into "
    for i in range(0, len(dec_list)):
        a=str(dec_list[i][0])
        b=str(dec_list[i][1])
        chain+= "("+ a + "," + b +")"
    print chain    
    return dec_list

decomposition([0,2,1])  

decomposition([1,2,0])   


decomposition([3,1,2,0])