Discussion:Permutation

La définition

par n-uplet d'un ensemble à n éléments ne me paraissait pas correcte et je l'ai écartée : il y a autant de permutations que de n-uplets, c'est vrai. Mais si l'ensemble de n éléments est sans ordre, il n'y a aucune façon canonique de définir une permutation à partir d'un simple n-uplet. Je pense qu'il s'agit d'une ancienne définition, qui n'a plus cours ? si je me trompe il faudrait la réintroduire séparément car elle provoque une confusion terrible dans les idées Peps 20 mai 2006

organisation des articles sur les permutations

voir Discuter:Groupe symétrique Peps 4 juin 2006

Décomposition d'une permutation en produit de transposition...

Il est dit dans l'article qu'une permutation est décomposable en un produit de transposition. Il me semble que ce n'est vrai que s'il s'agit de la permutation d'un ensemble fini : par exemple u(2n) = 2n+1, u(2n+1)=2n, qui inverse les pairs et impairs consécutifs est bien une permutation de N. Il me semble évident qu'on ne peut pas la décomposer un un nombre fini de transposition... message non signé du 9 avril 2010 à 11:34 de 85.69.80.211 (d · c · b)

Exact, merci, j'ai rajouté "de support fini" (le support est défini plus haut). Anne, 9/4/2010 à 15 h 04

Nombre minimum de transpositions

"le nombre minimum de transpositions nécessaires pour écrire une permutation donnée est exactement celui obtenu avec cet algorithme."

Ce n'est pas franchement évident. Une référence vers la preuve serait utile (ou, éventuellement, la preuve elle-même). — Le message qui précède, non signé, a été déposé par un utilisateur sous l’IP 78.229.106.132 (discuter), le 21 juin 2013 à 08:44.

Algorithme de décomposition

°L'algorithme de décomposition présenté dans l'article permutation, est incorrect. L'algorithme correct montrant que toute permutation de n éléments est obtenue par au plus n-1 transpositions est en fait le tri par sélection. L'échange de ce tri entre t[i] et t[min] correspond à la transposition (i,min). Le tri fait au plus n-1 échanges donc trouve au plus n-1 transpositions. La permutation initiale, est représentée par le tableau t[1]...t[n]. Les transpositions, pour obtenir cette permutation, doivent être appliquées dans l'ordre inverse de celui où elles sont trouvées par ce tri. Par exemple pour trier le tableau 2,5,4,3,1, on effectue dans l'ordre la suite d'échanges (1,5),(2,5),(3,4) donc la permutation 2,5,4,3,1 vaut (3,4)o(2,5)o(1,5). --Liviusbarbatus (discuter) 16 septembre 2017 à 21:46 (CEST)

L'algorithme de décomposition présenté dans l'article permutation est correct et donne justement, sur l'exemple du « tableau 2,5,4,3,1 », c'est-à-dire de la permutation (1 2 5)(3 4), la décomposition (3 4)(2 5)(1 5) une décomposition en trois transpositions. Anne, 17/9, 0 h 42, modifié à 12 h 34

Je ne suis pas d'accord avec vous, dans l'algorithme proposé, il faudrait écrire $k=\min\{\sigma (s)|1\leq s\leq n,\sigma (s)\neq s\}$ au lieu de $k=\min\{s,1\leq s\leq n,\sigma (s)\neq s\}$ — Le message qui précède, non signé, a été déposé par Liviusbarbatus (discuter), le 17 septembre 2017 à 09:42 (CEST)

Ça donnerait exactement le même k (parce que l'ensemble des points non fixes est stable) mais c'est plus clair tel quel. Rectif de mon erreur de cette nuit dans le calcul de l'exemple : la décomposition de (1 2 5)(3 4) fournie par l'algorithme de l'article n'est pas (3 4)(2 5)(1 5) mais (1 2)(2 5)(3 4). Voici un exemple de référence pour l'analogue (en remplaçant min par max) de l'algorithme de l'article, qui est correct et fait au plus n-1 échanges. Anne, 17/9, 12 h 34

Finalement je suis d'accord avec vous, sur le fait que l'algorithme de décomposition est correct. Il suffit de choisir n'importe quel $k$ tel que $\sigma (k)\neq k$. En effet après l'application de la transposition $(k,\sigma (k))$ à la permutation $\sigma$, la permutation $\sigma _{1}$ a un nouveau point fixe $\sigma (k)$. Cela prouve aussi que l'algorithme se termine, puisque le nombre de points fixes augmente de 1 à chaque appel de l'algorithme. Le seul désaccord avec vous reste que ça ne donne pas nécessairement le même k. Par exemple avec le même exemple 2,5,4,3,1 la première transposition est une transposition parmi les transpositions (2,1),(5,2),(4,3),(3,4),(1,5) chacune d'entre elles augmente de 1 le nombre de points fixes.

Je serais en faveur d'une légère modification de l'algorithme de décomposition, mettant en évidence que le choix arbitraire de k parmi les s tels que $\sigma (s)\neq s$ et surtout le fait que $\sigma _{1}(\sigma (k))=\sigma (k)$, donc que le nombre de points fixes de $\sigma _{1}$ est strictement plus grand que celui de $\sigma$.

Je relève une erreur mineure dans l'algorithme de décomposition. Sur la première ligne de l'algorithme, on parle d'une permutation $\sigma$ de support fini {1..n}. Au lieu de support, il faut dire de domaine {1..n}.

Liviusbarbatus, 17/9, 14h48

Restes chinois

En l'absence de sources, la prétendue application au théorème des restes chinois, ajoutée en 2008, me semble un TI à virer. Anne, 22/3/2022

English: Permutation universe (causal closure) vs Everettist (many-worlds interpretation) and multiaxiomatical algorithm of universes (most different universes have different physics/ physical foundations)

• https://www.quantamagazine.org/where-do-space-time-and-gravity-come-from-20220504/

Quanta Magazine has many related articles about the nature of the possible universes and also about our own universe.

Neither mathematically nor observationally/factually we live in a permutation universe = closed system = causal closure without multifurcating foundations see: David Tong on Quanta Magazine and YouTube