import time 
from pylab import *

### Question 1) ###

def Liste_Permutations(n) :
    """ renvoie la liste des permutations sur Z/nZ """
    if n==1 :
        return [[0]]
    else :
        L_Temp=Liste_Permutations(n-1)
        M=[]
        for L in L_Temp :
            for k in range(n) :
                M.append(L[:k]+[n-1]+L[k:])
        return M

# print(Liste_Permutations(2))

### Question 2) ###

def Inverse(sigma) :
    """ calcule l'inverse de sigma """
    s_temp=[]
    for k in range(len(sigma)) :
        for j in range(len(sigma)) :
            if sigma[j]==k :
                s_temp.append(j)
                break
    return s_temp

sigma=[3,2,1,4,6,0,8,7,5]
# print(Inverse(sigma))
    
### Question 3) ###

def Rond(sigma_1,sigma_2) :
    """ calcule la composition sigma_1 rond sigma_2 dans S_n"""
    return [sigma_1[sigma_2[k]] for k in range(len(sigma_2))]

sigma_1=[0,2,1,3]
sigma_2=[2,1,3,0]
# print(Rond(sigma_1,sigma_2))

### Question 4) ###

def Decomposition_Transpositions(sigma) :
    """ fournit une décomposition en transpositions """
    if len(sigma)==1 :
        return []
    else :
        n=len(sigma)
        if sigma[-1]==n-1 :
            return Decomposition_Transpositions(sigma[:-1])
        else :
            k=sigma[-1]
            tau=list(range(k))+[n-1]+list(range(k+1,n-1))+[k]
            L=Decomposition_Transpositions(Rond(tau,sigma)[:-1])
            return [[k,n-1]]+L
            
sigma=[7,6,2,0,8,1,3,4,5] # OK

# print(Decomposition_Transpositions(sigma)) # OK
            
### Question 5) ###

def Decomposition_Cycles(sigma) :
    """ effectue la décomposition en cylces à supports disjoints """
    n=len(sigma)
    L=list(range(n))
    L_Cycles=[]
    while L!=[] :
        k=L[0]
        L_Temp=[k]
        while L_Temp.count(sigma[k])==0 :
            L_Temp.append(sigma[k])
            k=sigma[k]
        if len(L_Temp)>1 :
            L_Cycles.append(L_Temp)
        for j in L_Temp :
            L.remove(j)
    return " rond ".join(str(c) for c in L_Cycles)
    
sigma=[2,0,10,7,6,3,4,8,5,9,1]
# print(Decomposition_Cycles(sigma)) # ok

### Question 6) ###

### Méthode déterministe ###

def Calcul_Exact(n) :
    """ calcule la probabilité exacte de commutativité """
    L=Liste_Permutations(n) 
    compteur_possible=0
    compteur_favorable=0
    for s in L :
        for r in L :
            if Rond(r,s)==Rond(s,r) :
                compteur_favorable+=1
            compteur_possible+=1
    return compteur_favorable/compteur_possible

# for k in range(1,7) :
#     print("Probabilité sur S_"+str(k)+" de commutativité :", Calcul_Exact(k))

### Méthode probabiliste ###
from random import *

def Calcul_Approx(n) :
    """ calcule une valeur approchée sur 10000 essais """
    L=Liste_Permutations(n) 
    N=len(L)
    compteur=0
    for j in range(100000) :
        s=L[randint(0,N-1)]
        r=L[randint(0,N-1)]
        if Rond(r,s)==Rond(s,r) :
            compteur+=1
    return compteur/100000
   
    
# for k in range(1,8) :
#     print("Probabilité  approchée sur S_"+str(k)+" de commutativité :", Calcul_Approx(k))

### Comparaison des deux méthodes ###


def Traces(n) :
    """ affiche les temps de calculs """
    LX=list(range(1,n+1))
    L_exact,L_approx=[],[]
    for k in LX :
        t_0=time.clock()
        Calcul_Exact(k)
        t_1=time.clock()
        L_exact.append(log(t_1-t_0))
    for l in LX :
        t_2=time.clock()
        Calcul_Approx(l)
        t_3=time.clock()
        L_approx.append(log(t_3-t_2))
    figure()
    plot(LX,L_exact,color="blue",marker="o")
    plot(LX,L_approx,color="magenta",marker="o")
    legend(('Calcul exact','Calcul approché'),'lower right',shadow=True)
    show()
Traces(6)