Une augmentation d'entropie

[tournesol]

Merci à toi .
Comment construis tu num(paquet)?

[GaBuZoMeu]

Que ne comprends-tu pas dans le code python ?

[tournesol]

Tout . Je reformule ma question .
Comment peut on construire une bijection de Sn dans [0 , n!-1]
En écrivant la question je me rappelle que nous en avons discuté dans un autre fil .
On appelle cela un code de ???????????amoins que je confonde avec autre chose .

[GaBuZoMeu]

Oui, je me souviens qu'on en avait discuté. Mais je ne souviens plus des détails, et là j'ai bricolé quelque chose (qui est peut-être la même chose). Le code python me semble pourtant assez explicite.

Code: Tout sélectionner

    # numérotation d'un paquet
    def Num(Paquet):

La procédure Num admet en entrée une liste de longueur 5 (nommée Paquet) qui est une permutation de [1,2,3,4,5]. On ne vérifie pas que c'est bien une permutation.

Code: Tout sélectionner

        Reste=Paquet.copy()

On fait une copie de la liste Paquet, qu'on appelle Reste. Cette dernière liste va être modifiée au cours de la procédure pour se réduire à peau de chagrin.

Code: Tout sélectionner

        ind=0

On introduit une variable ind qu'on initialise à 0. On va modifier cette variable pour obtenir à la fin le numéro de Paquet.

Code: Tout sélectionner

        for i in range(1,5):

On rentre maintenant dans une boucle. Le compteur de boucle est i qui va de 1 (compris) à 5 (non compris). L'indentation augmente pour signifier qu'on est dans la boucle.

Code: Tout sélectionner

            ind=(ind+Reste.index(i))*(5-i)

On cherche dans la liste Reste où se trouve le nombre i : Reste.index(i) renvoie le rang de i dans la liste Reste, sachant que la numérotation du rang commence à 0 (si i est en 3e place, la commande renvoie 2). On ajoute ce nombre à la valeur précédente de ind et on multiplie le tout par 5-i pour obtenir la nouvelle valeur de ind.

Code: Tout sélectionner

            Reste.remove(i)

On modifie la liste Reste en supprimant i de la liste. On retourne dans la boucle en incrémentant i de 1. On sort avant d'atteindre 5.

Code: Tout sélectionner

        return ind

On est sorti de la boucle (l'indentation a diminué) et on renvoie alors la dernière valeur de ind : c'est ça le numéro de Paquet.

PS. Il s'agissait du code de Lehmer, et ça se trouve dans ce fil. La procédure explicitée ci-dessus est effectivement dans l'esprit du code de Lehmer.

[tournesol]

Merci à toi . J'ai constaté que ton algorithme donne le rang de la permutation inverse ce qui ne pose d'ailleurs aucun pb puisque s->s^(-1) est une paramétrisation bijective de Sn .

[GaBuZoMeu]

Que veux-tu dire ? La procédure donne un numéro à une permutation.
Tu dis que c'est "le rang de la permutation inverse". De quel rang parles-tu ?

[tournesol]

J'ai un peu regardé dans la litterature :
12345 a la rang 0
12354 a le rang 1
etc.
54321 a le rang 119
ton algorithme appliqué à 35214 donne 85
ton algorithme appliqué à 43152 donne 68
le rang de 35214 est 2x4!+3×3!+1×2!+0×1!=68
le rang de 43152 est 3×4!+2×3!+0×2!+1×1!=85

[GaBuZoMeu]

Il y aurait un rang canonique pour les permutations ?

[tournesol]

Je te vois venir . Il vaut mieux que je révise la définition de canonique avant de te répondre .
En particulier ce rang doit être indépendant de ?????????

[tournesol]

Il semble que non .La révision de la def m'a rien apporté de plus.
Soit E un ensemble fini de cardinal n et soit f une bijection de E dans [1;n]
f permet d'associer à toute permutation s de E l'élément de Sn
On a PAS en général rang ()=rang () si g est une autre bijection de E dans [1;n] .
En particulier , pour E=[1,n] , le rang n'est pas conservé par les automorphismes intérieurs .
Donc pas de rang canonique .
Par contre
La signature est canonique .
Si est le nombre de cycles d'ordre i de la décomposition(non canonique ?) en produit de cycles disjoints , est canonique , étant la famille strictement croissante des nombres premiers .
Mais à contrario , on peut dire que le rang est canonique comme une base est canonique .
La base est imposée comme naturelle , comme l'ordre croissant s'impose comme l'ordre naturel .
On peut interpreter le code d'une permutation(comme 32415) comme l'écriture d'un entier en base n+1 , et l'ordre sur les entiers induit un ordre sur Sn .
?????????????????

[GaBuZoMeu]

Il y a pas mal de façons possibles de ranger , et aucune n'a de raison valable d'être appelée canonique.
J'ai choisi ma numérotation parce qu'elle me semblait la plus facile à coder, c'est tout.

[tournesol]

Encore merci pour toutes tes explications .

[GaBuZoMeu]

Avec plaisir.