#-*-coding:utf8-*-
from copy import deepcopy
from random import seed, shuffle 


'''
Le but de ce TP est de réaliser un algorithme de chiffrement symétrique de type
permutation : on mélange les lettres du message d'origine.

Il nous faudra donc commencer par définir des fonctions de permutations, c'est-à-dire
des bijections de l'ensemble {1,2,...,n} dans lui-même.

Dans ce qui suit, vous trouverez différentes fonctions, que vous devez compléter.

Vous devez :
 - changer le nom de ce fichier en nom_prenom.py, en remplaçant tous les caractères
   étranges de vos noms et prénoms par des _,
 - compléter le corps des fonctions ci-dessous, et ne rien modifier d'autre dans ce 
   fichier,
 - m'envoyer le fichier par mail à : christophe.guyeux@univ-fcomte.fr, à la fin de la
   séance de TP.

Bon courage !

'''



def est_permutation(L):
    '''
    Cette fonction teste si la liste L est la description d'une permutation
    de l'ensemble d'entiers [1,n].

    On rappelle qu'une permutation de E est une bijection de E dans E.

    Cette fonction renvoie donc vraie si et seulement si L contient une et 
    une seule fois tous les entiers de 1 à n, où n est la taille de L.

         >>> est_permutation([1,4,2,3])
         True
         >>> est_permutation([1,6,2,3])
         False
         >>> est_permutation([1,3,4])
         False
         
    '''
    return set(L) == set(range(1,len(L)+1))


assert est_permutation([1,4,2,3])
assert not est_permutation([1,5,2,3])
assert not est_permutation([1,2,1,3])






def transpose(i,j,L):
    '''
    Cette fonction construit de premiers exemples de permutations.

    Cette fonction transpose les éléments i et j de  la liste L :
       - l'élément en position i doit se retrouver en position j,
       - l'élément en position j doit se retrouver en position i,
    Le retour de la fonction est la nouvelle liste :

         >>> transpose(2,4,[1,2,3,4,5])
         [1,2,5,4,3]

    On vérifiera au préalable  que L est bien la description d'une permutation.

    '''
    assert est_permutation(L)
    L[i],L[j] = L[j],L[i]
    return L


assert transpose(2,4,[1,2,3,4,5]) == [1,2,5,4,3]
assert transpose(2,5,[1,2,3,4,5,6]) == [1,2,6,4,5,3]
assert transpose(2,5,[1,2,6,4,5,3]) == [1,2,3,4,5,6]






def permutation_circulaire(L,n):
    '''
    On construit ici un deuxième exemple de permutations élémentaires.

    Cette fonction effectue une permutation circulaire de la
    liste L : les n premiers éléments de L se retrouve à la fin 
    de L. Le retour est une liste.

         >>> permutation_circulaire([1,5,2,3,6,7],2)
         [2, 3, 6, 7, 1, 5]

    On vérifiera que L est bien la liste d'une permutation de [1,n].
    '''
    assert est_permutation(L)
    return L[n:]+L[:n]


assert permutation_circulaire([1,2,3,4,5,6],4) == [5,6,1,2,3,4]
assert permutation_circulaire([1,2,6,4,5,3],5) == [3, 1, 2, 6, 4, 5]
assert permutation_circulaire(range(1,5),0) == range(1,5)



def permutation(L):
    '''
    Construit la bijection de [1,n] dans lui-même dont L est la description
    sous forme de liste.

    Par exemple, si L est égale à [1,4,2,3], notre fonction doit envoyer :
      - 1 sur 1 (1 est le premier élément de la liste),
      - 2 sur 4 (le deuxième élément de la liste, c'est 4),
      - 3 sur 2,
      - 4 sur 3.

    Le retour de permutation est une fonction lambda.
        
        >>> f = permutation([3,1,4,2])
        >>> f(2)
        1
        >>> f(3)
        4
    '''
    assert est_permutation(L)
    return lambda k : L[k-1]



assert permutation([2,1,6,5,3,4])(3) == 6
assert permutation([2,1,6,5,3,4])(5) == 3
assert permutation([2,1,5,3,4])(3) == 5





def permutation_inverse(L):
    '''
    Construit la bijection réciproque de la permutation associée à L.

    Comme la permutation [1,4,2,3] envoie :
      - 1 sur 1,
      - 2 sur 4,
      - 3 sur 2,
      - 4 sur 3,
    sa permutation réciproque devra envoyer (on inverse les lignes ci-dessus) :
      - 1 sur 1,
      - 4 sur 2,
      - 2 sur 3,
      - 3 sur 4.

    Elle correspond donc à la permutation [1,3,4,2]. On constate que l'image d'un
    entier k par cette réciproque correspond à l'indice de k dans L :
      - 1 apparaît en première position dans L=[1,4,2,3], donc son image est 1,
      - 2 apparaît en troisième position dans L=[1,4,2,3], donc son image est 3,
      - 3 apparaît en quatrième position dans L=[1,4,2,3], donc son image est 4,
      - 4 apparaît en deuxième position dans L=[1,4,2,3], donc son image est 2.

         >>> permutation_inverse([1,3,4,2])
         [1,4,2,3]
         >>> permutation_inverse([1,4,2,3])
         [1,3,4,2]
    '''
    assert est_permutation(L)
    return [L.index(k)+1 for k in range(1,len(L)+1)]


assert permutation_inverse([1,3,4,2]) == [1, 4, 2, 3]
assert permutation_inverse([1,2]) == [1,2]
assert permutation_inverse([1,6,3,2,4,5]) == [1, 4, 3, 5, 6, 2]






def permutation_aleatoire(n, cle):
    '''
    Cette fonction crée une permutation aléatoire des entiers de 1 à n.

    L'argument cle fournit la graine au générateur de fonctions aléatoires : si vous
    mettez deux fois la même clé, alors vous aurez deux fois la même permutation.

    Pour que cela se passe ainsi, vous devez commencer cette fonction par : seed(cle)

    Cette clé est une chaîne de caractères. 

        >>> permutation_aleatoire(5, "cle_secrete")
        [1, 5, 4, 3, 2]
        >>> permutation_aleatoire(15, "autre cle")
        [7, 9, 8, 6, 5, 11, 15, 14, 12, 3, 4, 10, 1, 13, 2]

    '''
    seed(cle)
    L = range(1,n+1)
    shuffle(L)
    return L



assert permutation_aleatoire(10, "cle_secrete") == [5, 10, 1, 2, 8, 4, 9, 7, 6, 3]
assert permutation_aleatoire(10, "cle") == [5, 2, 3, 7, 6, 10, 4, 9, 1, 8]
assert permutation_aleatoire(10, "secrete") == [4, 10, 1, 3, 5, 8, 2, 6, 9, 7]






def chiffrement(message, cle):
    '''
    Réalise un chiffrement par permutation.
        - message est une chaîne de caractères, que l'on veut chiffrer,
        - cle est la clé de chiffrement (une chaîne de caractères),
        - le retour est le cryptogramme (une chaîne de caractères).

    A partir de la clé de chiffrement fournie, on construit une permutation
    aléatoire f de la même taille que le message (avec la fonction ci-dessus).

    La première lettre du message est envoyée en position f(1), où f est
    la permutation décrite par la liste aléatoire. La deuxième lettre du message
    est envoyée en f(2), etc.

    Comme f est une bijection, on a bien un algorithme de chiffrement.

        >>> chiffrement('coucou', "cle secrete")
        uooucc
    
    '''
    f = permutation(permutation_aleatoire(len(message),cle))
    retour = range(len(message))
    for k in range(len(message)):
        retour[k] = message[f(k+1)-1]
    return ''.join(retour)


assert chiffrement('coucou', "cle secrete") == 'uooucc'
assert chiffrement('tagada jones','cle') == 'g sodajtaean'
assert chiffrement('tutukakititicaca','azerty') == 'aiikttiutktccaau'





def dechiffrement(message, cle):
    '''
    Réalise le déchiffrement du cryptogramme considéré, en utilisant la même
    clé secrète.

    On génère la permutation pseudo-aléatoire associée à cette clé secrete, qui a
    la même taille que le cryptogramme donné en premier argument. On calcule la 
    permutation réciproque de cette permutation, que l'on applique au cryptograme.

        >>> dechiffrement('uooucc', "cle secrete")
        coucou

'''
    f = permutation(permutation_inverse(permutation_aleatoire(len(message),cle)))
    retour = range(len(message))
    for k in range(len(message)):
        retour[k] = message[f(k+1)-1]
    return ''.join(retour)




assert dechiffrement('g sodajtaean','cle') == 'tagada jones'
assert dechiffrement('aiikttiutktccaau','azerty') == 'tutukakititicaca'
assert dechiffrement('uooucc', "cle secrete" ) == 'coucou'