Classe Permutation et décomposition en transitions

On reprend le notebook qui introduit la classe permutation pour la compléter avec pour objectifs de décomposer une permutation en transposition (l’échange de deux élements dans un tableau).

Composition

Lorsque la décomposition d’une permutation sera implémentée, il faudra vérifier (tester) qu’elle fonctionne. Pour cela, il faut être capable de composer deux permutations. C’est l’objet de la méthode compose ci-dessous.

class Permutation:
    def __init__(self, sigma_or_n: int | list[int]):
        if isinstance(sigma_or_n, int):
            self.sigma = list(range(sigma_or_n))
        elif isinstance(sigma_or_n, list):
            self.sigma = sigma_or_n
        else:
            # Ce code produit une erreur dès que le type du paramètre d'entrée
            # n'est ni un entier ni une liste.
            raise TypeError(f"unexpected type {type(sigma_or_n)}")

    def __str__(self) -> str:
        return " ".join([str(i) for i in self.sigma])

    def applique(self, ensemble: list) -> list:
        nouvel_ensemble = [None for i in ensemble]
        for position, s in enumerate(self.sigma):
            nouvel_ensemble[position] = ensemble[s]
        return nouvel_ensemble

    def compose(self, p2):
        """
        Composer deux permutations revient à appliquer la seconde permutation
        sur l'ensemble sigma qui définit la première permutation.
        """
        perm = p2.applique(self.sigma)
        return Permutation(perm)


def test_compose():
    """
    On test sur des cas simples, la permutation de deux éléments
    ou encore l'applique de la même permutation trois fois.
    On peut aussi vérifier qu'un théorème est vrai. Le groupe des permutations
    de l'ensemble n étant fini, il existe un entier telle la permutation
    composée avec elle-même n fois aboutisse à la permutation identité.
    """
    p1 = Permutation([1, 0])
    assert p1.compose(p1).sigma == [0, 1]
    p2 = Permutation([2, 0, 1])
    assert p2.compose(p2.compose(p2)).sigma == [0, 1, 2]


test_compose()

Opérateur == et @

Tout fonctionne mais l’écriture est verbeuse. On souhaite la simplifier pour écrire p == [0, 1] au lieu de p.sigma == [0, 1]. Pour cela, il faut surcharger l’opérateur == et implémentation la méthode spéciale __eq__. On fait de même avec la composition, on veut écrire p1 @ p2 à la place de p1.compose(p2).

class Permutation:
    def __init__(self, sigma_or_n: int | list[int]):
        if isinstance(sigma_or_n, int):
            self.sigma = list(range(sigma_or_n))
        elif isinstance(sigma_or_n, list):
            self.sigma = sigma_or_n
        else:
            # Ce code produit une erreur dès que le type du paramètre d'entrée
            # n'est ni un entier ni une liste.
            raise TypeError(f"unexpected type {type(sigma_or_n)}")

    def __str__(self) -> str:
        return " ".join([str(i) for i in self.sigma])

    def applique(self, ensemble: list) -> list:
        nouvel_ensemble = [None for i in ensemble]
        for position, s in enumerate(self.sigma):
            nouvel_ensemble[position] = ensemble[s]
        return nouvel_ensemble

    def compose(self, p2):
        perm = p2.applique(self.sigma)
        return Permutation(perm)

    def __eq__(self, ens):
        """
        Cette méthode est appelée dès qu'on écrit `p == quelque chose`.
        """
        if isinstance(ens, list):
            # si ens est une liste...
            return self.sigma == ens
        # si ens est une instance de la classe Permutation...
        return self.sigma == ens.sigma

    def __matmul__(self, p):
        """
        Cette méthode est appelée dès qu'on écrit `p1 @ quelque chose`.
        """
        return self.compose(p)


def test_compose():
    """
    La fonction de test est plus lisible comme ceci.
    Mais c'est parfois une affaire de goût.
    """
    p1 = Permutation([1, 0])
    assert p1 @ p1 == [0, 1]
    p2 = Permutation([2, 0, 1])
    assert p2 @ p2 @ p2 == [0, 1, 2]


test_compose()

p = Permutation([0, 1])
p == [0, 1]

True

Décomposition

La décomposition d’une permutation en transposition consiste à chercher un élement qui n’est pas à sa position puis à le permutation avec celui qui l’est. Puis de continuer jusqu’à ce que tous les éléments soient à leur position.

position  0  1  2  3  4
sigma     0  2  3  4  1

Itération 1 : on permute 2 et 3 aux positions 1 et 2

position  0  1  2  3  4
sigma     0  3  2  4  1

Itération 2 : on permute 3 et 4 aux positions 1 et 3

position  0  1  2  3  4
sigma     0  4  2  3  1

Itération 3 : on permute 4 et 1 aux positions 1 et 4

position  0  1  2  3  4
sigma     0  1  2  3  4

On a fini. Les transpositions sont donc dans l’ordre inverse (1, 2), (1, 3), (1, 4).

class Permutation:
    def __init__(self, sigma_or_n: int | list[int]):
        if isinstance(sigma_or_n, int):
            self.sigma = list(range(sigma_or_n))
        elif isinstance(sigma_or_n, list):
            self.sigma = sigma_or_n
        else:
            # Ce code produit une erreur dès que le type du paramètre d'entrée
            # n'est ni un entier ni une liste.
            raise TypeError(f"unexpected type {type(sigma_or_n)}")

    def __str__(self) -> str:
        return " ".join([str(i) for i in self.sigma])

    def applique(self, ensemble: list) -> list:
        nouvel_ensemble = [None for i in ensemble]
        for position, s in enumerate(self.sigma):
            nouvel_ensemble[position] = ensemble[s]
        return nouvel_ensemble

    def compose(self, p2):
        perm = p2.applique(self.sigma)
        return Permutation(perm)

    def __eq__(self, ens):
        if isinstance(ens, list):
            return self.sigma == ens
        return self.sigma == ens.sigma

    def __matmul__(self, p):
        return self.compose(p)

    def decompose(self):
        transposition = []
        i = 0
        state = self.sigma.copy()
        while i < len(state):
            if state[i] == i:
                # l'élément est à sa position, on passe au suivant,
                # on sait que tous les éléments aux positions k < i
                # sont également à leur positions
                i += 1
            else:
                # l'élément n'est pas à sa position,
                # on permute avec celui à sa position,
                # on les grande dans une liste
                transposition.append((i, state[i]))
                v = state[i]
                state[v], state[i] = state[i], state[v]
        # on retourne la liste
        transposition.reverse()
        return transposition


def applique_decomposition_identite(n, decomposition):
    # On prend la permutation identité et on applique chaque transposition.
    p = Permutation(n)
    for i, j in decomposition:
        perm = list(range(n))
        perm[i], perm[j] = perm[j], perm[i]
        tr = Permutation(perm)
        p = p.compose(tr)
    return p


def test_decompose1():
    # On se sert de l'exemple donné ci-dessus pour tester la fonction.
    p = Permutation([0, 2, 3, 4, 1])
    dec = p.decompose()
    assert dec == [(1, 4), (1, 3), (1, 2)]


def test_decompose2():
    p = Permutation([0, 2, 3, 4, 1])
    dec = p.decompose()
    result = applique_decomposition_identite(len(p.sigma), dec)
    assert p == result


test_decompose1()
test_decompose2()

Transposition

Pour écrire le code de vérification, on a créé une transposition comme une instance de la classe Permutation :

perm = list(range(n))
perm[i], perm[j] = perm[j], perm[i]
tr = Permutation(perm)

On souhaite en faire une classe spéciale car ces permutations sont présentes dans de nombreux algorithmes. Mais comme une transposition est aussi une permutation, on souhaite créer une classe qui fonctionne de la même manière que la classe Permutation. C’est à cela que sert l’héritage. Ici, on a juste besoin de changer la façon dont une instance de classe Permutation est créée.

class Transposition(Permutation):
    def __init__(self, i, j, n):
        perm = list(range(n))
        perm[i], perm[j] = perm[j], perm[i]
        Permutation.__init__(
            self, perm
        )  # on appelle le constructeur de la classe parent = Permutation

    def __str__(self):
        return "TR: " + Permutation.__str__(
            self
        )  # on appelle la méthode de la classe parent = Permutation


t = Transposition(2, 3, 4)
print(t)
print(t @ t)

TR: 0 1 3 2
0 1 2 3

Un exemple court pour démêler ce qui est changé

L’exemple suivant permet de suivre quelle méthode appelle quelle autre lors d’un héritage.

class Parent:
    def A(self):
        print("A parent")
        self.C()

    def B(self):
        print("B parent")
        self.A()

    def C(self):
        print("C parent")


class Enfant(Parent):
    def B(self):
        print("B enfant")
        self.A()

    def C(self):
        print("C enfant")


p = Enfant()
p.B()

B enfant
A parent
C enfant

Python 3.x

Le langage python autorise d’autres écriture pour appeler la classe parent avec la fonction super.

class Transposition(Permutation):
    def __init__(self, i, j, n):
        perm = list(range(n))
        perm[i], perm[j] = perm[j], perm[i]
        super().__init__(
            perm
        )  # on appelle le constructeur de la classe parent = Permutation

    def __str__(self):
        return (
            "TR: " + super().__str__()
        )  # on appelle la méthode de la classe parent = Permutation


t = Transposition(2, 3, 4)
print(t)
print(t @ t)

TR: 0 1 3 2
0 1 2 3

Ou encore

class Transposition(Permutation):
    def __init__(self, i, j, n):
        perm = list(range(n))
        perm[i], perm[j] = perm[j], perm[i]
        super(Transposition, self).__init__(
            perm
        )  # on appelle le constructeur de la classe parent = Permutation

    def __str__(self):
        return (
            "TR: " + super(Transposition, self).__str__()
        )  # on appelle la méthode de la classe parent = Permutation


t = Transposition(2, 3, 4)
print(t)
print(t @ t)

TR: 0 1 3 2
0 1 2 3

La fonction super recherche le parent d’une classe. C’est donc un peu plus lent que de l’écrire de façon explicite. Voir aussi Python’s super() considered super!.

---

Notebook on github