from numpy import random as rd
import matplotlib.pyplot as plt
n = 10
E10 = [i for i in range(0,10)]
G = [1,3,5,7,9,1,3,5,7,9]
#G = [2*i+1 -n*((2*i+1)//n) for i in range(n)]
F = [3,4,5,6,7,8,9,0,1,2]
#F = [i+3 -n*((i+3)//n) for i in range(n)]

def compose(A,B):
    L = [A[bi] for bi in B] # Liste de composition
    return(L)

def aptfixe(A):
    """ Indique si une liste A contient un "point fixe" A[i] = i"""
    i = 0
    n = len(A)
    while i<n and A[i] != i:
        i = i+1
    return(i!=n)

def nptfixe(A):
    """Retourne le nombre de points fixes de la liste"""
    compteur = 0
    for i in range(len(A)):
        if i == A[i]:
            compteur = compteur+1
    return(compteur)

def Lptfixe(A):
    """Retourne la liste des points fixes de A"""
    Lfixe = []
    for i in range(len(A)):
        if i == A[i]:
            Lfixe.append(i)
    return(Lfixe)

def estpermut(A):
    n = len(A)
    M = [i for i in A]
    for i in range(n):
        j = 0
        while len(M)>j and M[j] != i :
            j=j+1
        if len(M)>j and M[j] == i:
            del(M[j])
    return(M == [])

def estpermut2(A): # Version corrigee vue en TP
    n = len(A)
    L = [0]*n
    for i in range(n):
        rang = A[i]
        if L[rang] ==0 :
            L[rang] = 1
        else:
            return False
    return True

def inverse(A):
    if estpermut2(A):
        Inv = [0 for i in A]
        for i in range(len(A)):
            Inv[A[i]] = i
    else:
        print("La liste n'est pas une permutation")
        return(A)
    return(Inv)

def init(n):
    L = [i for i in range(n)]
    a = rd.randint(n)
    R = L[0:a]+L[a+1:n]
    return(a,R)

def permutalea(n):
    L = [i for i in range(n)]
    R = []
    for i in range(n) :
        a = rd.randint(n-i)
        R.append(L[a])
        del(L[a])
    return(R)

def permutalea2(n):
    L = [i for i in range(n)]
    for i in range(n):
        a = rd.randint(n-i)
        L[a],L[n-1-i]=L[n-1-i],L[a]
    return(L)

def signature(A):
    P = 1
    n = len(A)
    for i in range(n):
        for j in range(n):
            if j!=i:
                P = P*(A[i]-A[j])/(i-j)
    return P
# Proche de 1
# L1sign = []
# L2sign = []
# L3sign = []
# T = [i for i in range(100)]
# for i in range(100):
#     L1 = permutalea(80)
#     L2 = permutalea2(80)
#     L3 = compose(L1,L2)
#     for i in '123':
#         exec('L'+i+'sign.append(signature(L'+i+'))')
# 
# for i in '123':
#     exec('plt.plot(T,L'+i+'sign)')
# plt.axis([0,100,0,2])
# plt.show()
n = 10
Sn = 0
for i in range(5000):
    Sn = Sn + nptfixe(permutalea2(n))
Sn = Sn/5000
print(Sn)
# Pour n = 10 : Sn = 1
# Pour n = 100 : Sn = 1