from numpy import random as rd
import matplotlib.pyplot as plt
n = 10
## Listes pour les tests :
En = [i for i in range(0,n)] # identite
G = [1,3,5,7,9,1,3,5,7,9] # Pas une permutation, un point fixe
#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] # Permutation, aucun point fixe.
#F = [i+3 -n*((i+3)//n) for i in range(n)]

## STRUCTURE DE DONNEE
#1
def compose(A,B):
#complexite lineaire
    L = [A[bi] for bi in B] # Liste de composition
    return(L)
#2
def aptfixe(A):
    """ Indique si une liste A contient un "point fixe" A[i] = i"""
#complexite lineaire
    i = 0
    n = len(A)
    while i<n and A[i] != i:
        i = i+1
    return(i!=n)
#3
def nptfixe(A):
    """Retourne le nombre de points fixes de la liste"""
#complexite lineaire
    compteur = 0
    for i in range(len(A)):
        if i == A[i]:
            compteur = compteur+1
    return(compteur)
#4
def Lptfixe(A):
    """Retourne la liste des points fixes de A"""
#complexite lineaire
    Lfixe = []
    for i in range(len(A)):
        if i == A[i]:
            Lfixe.append(i)
    return(Lfixe)
#6
def estpermut(A): # Fonctionne aussi si on est de E dans F de tailles differentes.
#complexite quadratique
    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, fonctionne uniquement si l'application est de E dans E.
#complexite lineaire
    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
#7
def inverse(A):
#complexite lineaire
    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)

## CREATION ALEATOIRE DE PERMUTATION
#1
def init(n):
#complexite lineaire mais tres faible
    L = [i for i in range(n)]
    a = rd.randint(n)
    R = L[0:a]+L[a+1:n]
    return(a,R)
#2
def permutalea(n):
#complexite lineaire
    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)
#3
def permutalea2(n):
#complexite lineaire
    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)

## 4 - COMPLEXITE

def chronometre(f,k):
    """"Chronometre pour une fonction demandant pour parametre une ou deux listes"""
    from time import clock
    T = []
    for i in range(1,501): # Quelques problemes se posent pour n = 0 en moyenne
        A = permutalea2(i)
        if k == 2 : #Deux arguments pour f
            B = permutalea2(i)
            c = clock()
            f(A,B)
        else:  #Un seul argument pour f
            c = clock()
            f(A)
        d = clock()
        T.append(d-c)
    plt.plot([i for i in range(500)],T)
    plt.show()

def chronometre2(f):
    """Chronometre pour une fonction ayant pour parametre n un cardinal"""
    from time import clock
    T = []
    for n in range(1,501):
        c = clock()
        f(n)
        d = clock()
        T.append(d-c)
    plt.plot([i for i in range(500)],T)
    plt.show()