# -*- coding: utf-8 -*-
"""
Created on Thu Mar  6 10:42:18 2014

@author: 
"""

#adapté du sujet X-MP-2011 (sur les permutations)

# Remarque : on prend E_n={0,...,n-1}


#PARTIE 1

#Q1
def estPermutation(t):
    n=len(t)
    image=n*[0]
    for i in range(n):
        image[t[i]]=1
    card_image=0
    for i in range(n):
        card_image+=1
    if card_image==n:
        return false
    else :
        return True
         
    

def composer(t,u):
    comp=len(u)*[0]#sert à initialiser
    for i in range(len(u)):
        comp[i]=t[u[i]]
    return(comp)
    
 
def inverser(t):
    inv=range(len(t))
    for i in range(len(t)):
        inv[t[i]]=i
    return(inv)
# Rem : linéaire 

def estIdentite(t):
    for i in range(len(t)):
        if t[i]!=i:
            return False
    return True
    

def ordre(t):
    ordre=1
    u=t
    while not(estIdentite(u)):
        u=composer(t,u)
        ordre=ordre+1
    return(ordre)    
  

def periode(t,i):
    per=1
    k=t[i]
    while k!=i:
        k=t[k]
        per=per+1
    return(per)  
    
#Q7
def estDansOrbite(t,i,j):
    k=i
    if k==j: 
        return True
    for l in range(len(t)):
        k=t[k]
        if k==j:
            return True
    return(False)    
        # A ameliorer avec un while 

#Q8
def estTransposition(t):
    n=0
    for l in range(len(t)):
        if t[l]!=l:
            n=n+1
        if n>2:
            return(False)
    if n==0:
        return(False)
    return(True)
    
#Q9
def estCycle(t):  
    nfixe=0
    for l in range(len(t)):
        if t[l]==l:
            nfixe=nfixe+1
        else:
            k=l
    if nfixe==len(t):
        return(False)
    #A ce stade, k est un point non fixe de la permutation        
    else:
        n=1
        x=t[k]
        while x!=k:
            n=n+1
            x=t[x]
        if n+nfixe==len(t):
            return(True)
        else:
            return(False)
 

    
def periodes(t):
    n=len(t)
    tab_per=n*[0]#initialisation 
    # tab_per est destiné à contenir le résultat final
    # chacun de ses coefficients est initialisé à 0
    for i in range(len(t)):
        if tab_per[i]==0:# si per[i]!=0, son ordre a déjà été déterminé
            orb=[i] 
            # orb est destiné à contenir les k qui sont dans l'orbite de i
            per=1# destiné à contenir la période  de i 
            k=i
            while t[k]!=i:
                k=t[k]
                orb.append(k)
                per=per+1
            for k in orb:
                tab_per[k]=per
    return(tab_per) 
# Rem :reste à montrer que c'est linéaire          
                
#Q11 
def kmodper(t,k):
    per=periode(t)
    kmodper=range(len(t))
    for p in per:
        l=k%p
        for i in range(len(t)): 
            if per[i]==p:
                kmodper[i]=l
    return(kmodper) 
     
def itererEfficace(t,k):
    itere=range(len(t))
    kmodp=kmodper(t,k)
    for i in range(len(t)):
        x=i
        for j in range(kmodp[i]):
            x=t[x]
        itere[i]=x    
    return(tuple(itere))  
             
#Q12 (1,0,3,4,2)               
   
# Q13

def pgcd(a,b):
    u=max(a,b)
    v=min(a,b)
    r=u%v
    while r>0:
        u=v
        v=r
        r=u%v
    return(v)    
# penser à la récursivité

#Q14 

def ppcm(a,b):
    return(a*b//pgcd(a,b))
    
#Q15
def ordreEfficace(t):
    per=periode(t)
    l=[]
    for i in range(len(t)):
        if per[i] not in l:
            l.append(per[i])
    ordre=1
    for a in l:
        ordre=ppcm(ordre,a)
    return ordre  
    
def signature(t):
    n=len(t)
    tab_per=n*[0]#initialisation 
    sign=1#reçoit le résultat
    # tab_per est destiné à contenir les périodes
    # chacun de ses coefficients est initialisé à 0
    #on n'a pas besoin de ce résultat final, mais ce tableau est utilisé pour savoir quelles
    #valeurs i ont déjà été traitées
    for i in range(len(t)):
        if tab_per[i]==0:# si per[i]!=0, son ordre a déjà été déterminé
            orb=[i] 
            # orb est destiné à contenir les k qui sont dans l'orbite de i
            per=1# destiné à contenir la période  de i 
            k=i
            while t[k]!=i:
                k=t[k]
                orb.append(k)
                per=per+1
            for k in orb:
                tab_per[k]=per
            sign=sign*((-1)**(per-1))
    return(sign)