TP — Permutations¶

Travaux pratiques · MPSI (tronc commun) · 2021-2022 · Python

Ce TP est un TP intermédiaire si vous avez fini intégralement les deux TP précédents sur les tris et le rendu de monnaie.

On considère ici des permutations de \(\range{0}{n-1} = \{0, 1, \dots, n-1\}\), c'est-à-dire des éléments de \(\mathfrak{S}_n\) (c'est un S en gothique, on écrira donc Sn dans les commentaires en Python) l'ensemble des bijections de \(\range{0}{n-1}\) dans lui-même. Remarque : en mathématiques, on utilise en général des permutations de \(\range{1}{n}\) mais le fait de commencer par 0 permettra d'utiliser directement ces valeurs comme indices.

Pour représenter \(\sigma \in \mathfrak{S}_n\), on va utiliser un tableau \(t_\sigma = [\sigma(0), \sigma(1), \dots, \sigma(n-1)]\), c'est-à-dire que la valeur \(\sigma(i)\) est à l'indice \(i\) dans \(t_\sigma\) :

\[ \forall i \in \range{0}{n-1}, \sigma(i) = t_\sigma[i] \]

Le groupe \((\mathfrak{S}_n, \circ)\)¶

Comme les permutations ont même ensemble de départ et d'arrivée, on peut les composer et comme elles sont bijectives, la composée l'est également. Ainsi \(\mathfrak{S}_n\) est stable par \(\circ\). De plus, l'identité est une permutation ainsi que la réciproque d'une permutation.

Question 1

def identite(n):
    # renvoie la permutation identité de Sn

Corrigé

def identite(n):
    # renvoie la permutation identité de Sn
    p = []
    for i in range(n):
        p.append(i)
    return p

Question 2

def compose(sigma, tau):
    # renvoie sigma o tau la composée des deux permutations de Sn
    # Cette fonction sera toujours appelée avec des permutations portant sur les
    # mêmes éléments, il n'y a rien à vérifier

Corrigé

def compose(sigma, tau):
    # renvoie sigma o tau la composée des deux permutations de Sn
    # Cette fonction sera toujours appelée avec des permutations portant sur les
    # mêmes éléments, il n'y a rien à vérifier
    n = len(sigma)
    p = []
    for i in range(n):
        p.append(sigma[tau[i]])
    return p

Question 3

def inverse(sigma):
    # renvoie la permutation inverse de sigma

Corrigé

def inverse(sigma):
    # renvoie la permutation inverse de sigma
    n = len(sigma)
    p = [ 0 ] * n
    for i in range(n):
        p[sigma[i]] = i
    return p

# écrivez vos tests ici pour vous assurer que vos fonctions fonctionnent

Question 4

def iter(sigma, k):
    # renvoie la permutation sigma^k= sigma o ... o sigma
    # on pourra faire une fonction récursive

Corrigé

def iter(sigma, k):
    # renvoie la permutation sigma^k= sigma o ... o sigma
    # on pourra faire une fonction récursive
    if k == 0:
        return identite(len(sigma))
    return compose(sigma, iter(sigma, k-1))

# écrivez vos tests ici pour vous assurer que vos fonctions fonctionnent

Pour vérifier si un tableau d'entiers est une permutation, on peut créer un tableau de n = len(t) booléens valant False et mettre True à l'indice p quand t[i] = p pour i parcourant les indices. Attention t[i] peut très bien ne pas être une valeur dans \(\range{0}{n-1}\).

Question 5

def test_permutation(t):
    # renvoie un booléen (True ou False) indiquant si le
    # tableau t est celui d'une permutation

Corrigé

def test_permutation(t):
    # renvoie un booléen (True ou False) indiquant si le
    # tableau t est celui d'une permutation
    n = len(t)
    valid = [ False ] * n
    for i in range(n):
        p = t[i]
        if 0 <= p < n:
            valid[p] = True
    for b in valid:
        if not b:
            return False
    return True

# écrivez vos tests ici pour vous assurer que vos fonctions fonctionnent

Si \(\sigma\) est une permutation de \(\mathfrak{S}_n\) et \(t\) un tableau à \(n\) éléments, il est possible de considérer le tableau permuté de \(t\) par \(\sigma\), noté \(\sigma.t\) par extension et défini par \(\sigma.t[i] = t[\sigma(i)]\) pour tout indice \(i\). Ainsi si \(\sigma\) est la permutation correspondant au tableau [3,1,2,0] et t = ['a','b','c','d'] alors \(\sigma.t\) = ['d','b','c','a'].

Question 6

def action(sigma, t):
    # renvoie le tableau sigma . t
    # on suppose t et sigma de même longueur

Corrigé

def action(sigma, t):
    # renvoie le tableau sigma . t
    # on suppose t et sigma de même longueur
    st = []
    n = len(t)
    for i in range(n):
        st.append(t[sigma[i]])
    return st

# écrivez vos tests ici pour vous assurer que vos fonctions fonctionnent

Orbite¶

Soit \(\sigma \in \mathfrak{S}_n\) et \(i \in \range{0}{n-1}\). On note \(\text{Orb}_\sigma(i) = \{i, \sigma(i), \sigma^2(i), \dots\}\). Cet ensemble est nécessairement fini, on peut donc le représenter par un tableau d'entiers.

Par exemple, si on considère \(\sigma\) = [5,2,4,1,3,0] on a \(\text{Orb}_\sigma(0) = \{0, 5\} = \text{Orb}_\sigma(5)\) et \(\text{Orb}_\sigma(1) = \{1, 2, 4, 3\}\).

Question 7

def orbite(sigma, i):
    # renvoie Orb_sigma(i) comme un tableau sans répétitions

Corrigé

def orbite(sigma, i):
    # renvoie Orb_sigma(i) comme un tableau sans répétitions
    o = [i]
    k = i
    while sigma[k] != i:
        k = sigma[k]
        o.append(k)
    return o

# écrivez vos tests ici pour vous assurer que vos fonctions fonctionnent

Les orbites de \(\sigma\) forment une partition de \(\range{0}{n-1}\). Cela signifie que chaque élément est présent dans une orbite et une seule.

Question 8

def orbites(sigma):
    # renvoie les orbites de sigma dans un tableau d'orbites sans répétitions

Corrigé

def orbites(sigma):
    # renvoie les orbites de sigma dans un tableau d'orbites sans répétitions
    n = len(sigma)
    traites = [ False ] * n
    orbites = []
    for i in range(n):
        if not traites[i]:
            traites[i] = True
            o = [i]
            k = i
            while sigma[k] != i:
                k = sigma[k]
                traites[k] = True
                o.append(k)
            orbites.append(o)
    return orbites

>>> orbites([5,2,4,1,3,0]) # doit renvoyer par exemple [[0, 5], [1, 2, 4, 3]]
[[0, 5], [1, 2, 4, 3]]

Génération des permutations¶

Il peut être intéressant de générer toutes les permutations pour des problèmes d'exploration exhaustive comme on en verra en deuxième année. Pour le moment, imaginons qu'on souhaite casser un code, une manière bête mais sûre d'y arriver est de tous les tester.

Il existe de nombreuses approches, dont certaines sont très astucieuses pour économiser l'espace. On va voir ici une approche plus simple proche de celle vue dans le TP précédent.

On va prendre un point de vue plus proche de notre représentation en parlant de tableaux sans répétitions. On note \(P(E)\) l'ensemble des tableaux sans répétitions dont les éléments sont dans \(E\). On cherche donc à calculer \(P(\range{0}{n-1})\). Pour cela, on va remarquer que

\[ P(E) = \bigcup_{e \in E} \{ [e] + t \mid t \in P(E \setminus \{e\}) \} \]

Ici \(+\) est la concaténation des tableaux. On en déduit une fonction récursive d'énumération. On remarque \(P(\emptyset) = \{[]\}\).

Question 9

def retire(t, e):
    # renvoie un NOUVEAU tableau contenant les éléments de t sauf e

Corrigé

def retire(t, e):
    # renvoie un NOUVEAU tableau contenant les éléments de t sauf e
    tp = []
    for x in t:
        if x != e:
            tp.append( x )
    return tp

# écrivez vos tests ici pour vous assurer que vos fonctions fonctionnent

Question 10

def permutations(t):
    # renvoie P(t)

Corrigé

def permutations(t):
    # renvoie P(t)
    if t == []:
        return [ [] ]
    p = []
    for e in t:
        for tp in permutations(retire(t, e)):
            p.append( [e] + tp )
    return p

>>> permutations([0,1,2])
[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]