{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Permutations\n", "\n", "Marc Lorenzi\n", "\n", "31 mars 2023" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import random\n", "import math\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Introduction" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.1 Permutations et Python" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans tout ce notebook, $n$ désigne un entier naturel. On note $\\mathfrak S_n=\\mathfrak S([|0,n-1|])$ l'ensemble des permutations de l'ensemble $[|0,n-1|]$.\n", "\n", "On représente en Python une permutation $\\sigma\\in\\mathfrak S_n$ par la liste $[\\sigma(0),\\ldots,\\sigma(n-1)]$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `print_perm` permet d'afficher de façon agréable une permutation $s$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def print_perm(s):\n", " n = len(s)\n", " ln = n * '+---' + '+'\n", " print(ln)\n", " for k in range(n):\n", " print('|%2d ' % k, end='')\n", " print('|')\n", " print(ln)\n", " for k in range(n):\n", " print('|%2d ' % s[k], end='')\n", " print('|')\n", " print(ln) " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print_perm([7, 1, 2, 4, 3, 6, 5, 8, 10, 9, 0])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.2 Permutations aléatoires" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il sera bien utile d'avoir pour nos tests une fonction qui renvoie une permutation « aléatoire ». La fonction `random_perm` prend en paramètre un entier $n$ et renvoie une permutation de $\\mathfrak S_n$. L'algorithme utilisé est *l'algorithme de Fisher-Yates*. \n", "\n", "Munissons $\\mathfrak S_n$ de la probabilité uniforme $\\mathbb P$. La fonction `random_perm` peut être vue comme une variable aléatoire $X$ à valeurs dans $\\mathfrak S_n$. On peut montrer (nous ne le ferons pas ici) que pour toute permutation $\\sigma\\in\\mathfrak S_n$, on a $\\mathbb P(X=\\sigma)=\\frac 1 {n!}$. Comme le cardinal de $\\mathfrak S_n$ est $|\\mathfrak S_n|=\\frac 1{n!}$, la variable aléatoire $X$ suit une loi uniforme." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def random_perm(n):\n", " s = list(range(n))\n", " for i in range(n - 1, -1, -1):\n", " j = random.randint(i, n - 1)\n", " s[i], s[j] = s[j], s[i]\n", " return s" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = random_perm(15)\n", "print_perm(s)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Opérations sur les permutations" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$(\\mathfrak S_n,\\circ)$ est un groupe pour la composition des applications." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.1 Élément neutre" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `id` renvoie la permutation identité, neutre de $\\mathfrak S_n$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def id(n):\n", " return list(range(n))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print_perm(id(10))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.2 Produit" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `produit` renvoie la composée des deux permutations $s_1$ et $s_2$, supposées de même taille." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def produit(s1, s2):\n", " n = len(s1)\n", " return [s1[s2[k]] for k in range(n)]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print_perm(produit([1, 4, 0, 3, 2], [4, 0, 1, 3, 2]))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s1 = random_perm(10)\n", "s2 = random_perm(10)\n", "print_perm(s1)\n", "print_perm(s2)\n", "print_perm(produit(s1, s2))\n", "print_perm(produit(s2, s1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.3 Inverse" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `inverse` renvoie l'inverse de la permutation $s$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def inverse(s):\n", " n = len(s)\n", " s1 = n * [None]\n", " for k in range(n):\n", " s1[s[k]] = k\n", " return s1" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print_perm(inverse([5,3,1,2,0,4]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le produit d'une permutation et de son inverse est égal à $id$. Faisons un petit test." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s1 = random_perm(15)\n", "s2 = inverse(s1)\n", "print_perm(s1)\n", "print_perm(s2)\n", "print(produit(s1, s2) == id(15), produit(s2, s1) == id(15))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.4 Puissances" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Comme dans tous les groupes, on dispose dans $\\mathfrak S_n$ de la notion de puissance.\n", "\n", "La fonction `puissance` prend en paramètre une permutation $s$ et un entier relatif $n$. Elle renvoie $s^n$. Elle utilise l'algorithme d'exponentiation rapide." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def puissance(s, n):\n", " if n < 0: \n", " s = inverse(s)\n", " n = -n\n", " z = list(range(len(s)))\n", " while n > 0:\n", " if n % 2 == 1:\n", " z = produit(z, s)\n", " s = produit(s, s)\n", " n = n // 2\n", " return z" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = random_perm(15)\n", "print_perm(puissance(s, 123456789101112))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = random_perm(15)\n", "print_perm(puissance(s, -123456789101112))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = random_perm(15)\n", "print_perm(produit(puissance(s, 123456789101112), puissance(s, -123456789101112)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Décomposition en produit de cycles de supports disjoints" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Toute permutation se décompose en produit de cycles de supports disjoints. La décomposition est unique à l'ordre près des facteurs." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On représente en Python un cycle $\\gamma$ de longueur $k\\ge 2$ par une liste $[a_0\\ldots a_{k-1}]$, où $\\gamma(a_0)=a_1$, $\\gamma(a_1)=a_2$, $\\ldots\\gamma(a_{k-1})=a_0$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.1 Orbites" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `orbite` prend en paramètres une permutation $s$ et un entier $x$. Elle renvoie sous forme de liste l'orbite de $x$ suivant $s$, parcourue dans l'ordre. Le troisième paramètre, $e$, est optionnel. Si $e$ est différent de `None`, c'est un ensemble auquel on retire au fur et à mesure les éléments de l'orbite de $x$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def orbite(s, x, e=None):\n", " c = [x]\n", " y = s[x]\n", " while y != x:\n", " c.append(y)\n", " if e != None: e.remove(y)\n", " y = s[y]\n", " return c" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = random_perm(15)\n", "c = orbite(s, 0)\n", "print_perm(s)\n", "print(c)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.2 Décomposition en produit de cycles" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `vers_cycles` prend en paramètre une permutation $\\sigma$ et renvoie une liste de cycles dont le produit est $\\sigma$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def vers_cycles(s):\n", " n = len(s)\n", " cs = []\n", " e = set(range(n))\n", " while len(e) != 0:\n", " x = e.pop()\n", " c = orbite(s, x, e)\n", " if len(c) != 1: cs.append(c)\n", " return cs" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = random_perm(15)\n", "cs = vers_cycles(s)\n", "print_perm(s)\n", "print(cs)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.3 Recomposition" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `vers_permut` effectue l'opération inverse de `vers_cycles`. Elle prend en paramètre une liste de cycles (supposés de supports disjoints) et renvoie leur produit." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def vers_permut(cs, n):\n", " s = list(range(n))\n", " for c in cs:\n", " lc = len(c)\n", " for i in range(lc - 1):\n", " s[c[i]] = c[i + 1]\n", " s[c[lc - 1]] = c[0]\n", " return s " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vérifions que `vers_permut` est bien inverse à gauche de `vers_cycles`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s1 = random_perm(1000)\n", "cs = vers_cycles(s1)\n", "s2 = vers_permut(cs, 1000)\n", "print(s1 == s2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.4 Nombre d'orbites" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `nombre_orbites` prend en paramètre un permutation $s$. Elle renvoie un triplet $(n_1, n_2, n_3)$ où\n", "\n", "- $n_1$ est le nombre d'orbites de $s$ non réduites à un point\n", "- $n_2$ est le nombre de points fixes de $s$\n", "- $n_3 = n_1 + n_2$ est le nombre total d'orbites." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def nombre_orbites(s):\n", " cs = vers_cycles(s)\n", " n1 = len(cs)\n", " n2 = len(s)\n", " for c in cs: n2 = n2 - len(c)\n", " return (n1, n2, n1 + n2)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = random_perm(15)\n", "print_perm(s)\n", "print(vers_cycles(s))\n", "print(nombre_orbites(s))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Quelques statistiques" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nous allons dans cette section nous livrer à quelques statistiques concernant les orbites et les points fixes d'une permutation. Commençons par quelque chose de simple." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.1 Points fixes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Combien une permutation possède-t-elle de points fixes ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def nombre_points_fixes(s):\n", " return nombre_orbites(s)[1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `stats_points_fixes` renvoie une estimation du nombre « moyen » de points fixes d'une permutation de $\\mathfrak S_n$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def stats_points_fixes(n, N=1000):\n", " a = 0.\n", " for k in range(N):\n", " s = random_perm(n)\n", " a = a + nombre_points_fixes(s)\n", " return a / N" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "stats_points_fixes(100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Proposition vague.** Le nombre moyen de points fixes d'une permutation de $\\mathfrak S_n$ est égal à 1.\n", "\n", "Rendons tout d'abord la proposition moins vague. Munissons $\\mathfrak S_n$ de la probabilité uniforme $\\mathbb P$. Pour $i\\in[|0,n-1|]$, soit $X_i:\\mathfrak S_n\\longrightarrow\\mathbb R$ définie par $X_i(\\sigma)=1$ si $\\sigma(i)=i$ et $X_i(\\sigma)=0$ sinon. Posons enfin\n", "\n", "$$X=\\sum_{i=0}^{n-1}X_i$$\n", "\n", "Pour toute permutation $\\sigma\\in\\mathfrak S_n$, $X(\\sigma)$ est le nombre de points fixes de $\\sigma$.\n", "\n", "**Proposition.** L'espérance de la variable aléatoire $X$ est $E(X)=1$.\n", "\n", "**Démonstration.** Pour tout $i\\in[|0,n-1|]$, $X_i$ suit une loi de Bernoulli. Le paramètre de cette loi est\n", "\n", "$$p_i=\\mathbb P(X_i=1)$$\n", "\n", "Considérons l'événement $A_i=\\{X_i=1\\}$. On a\n", "\n", "$$A_i=\\{\\sigma\\in\\mathfrak S_n:\\sigma(i)=i\\}$$\n", "\n", "On vérifie facilement que l'ensemble $A_i$ est en bijection avec $\\mathfrak S_{n-1}$. De là,\n", "\n", "$$p_i=\\mathbb P(A_i)=\\frac{|A_i|}{n!}=\\frac{(n-1)!}{n!}=\\frac 1 n$$\n", "\n", "Ainsi, $E(X_i)=\\frac 1 n$. Il ne reste plus qu'à utiliser la linéarité de l'espérance.\n", "\n", "$$E(X)=\\sum_{i=0}^{n-1}E(X_i)=1$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.2 Nombre d'orbites" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Généralisons un peu. Soit $k\\in[|1,n|]$. Combien une permutation $\\sigma\\in\\mathfrak S_n$ possède-t-elle d'orbites de cardinal $k$ ?\n", "\n", "Notons $C_k(\\sigma)$ le nombre d'orbites selon $\\sigma$ qui sont de cardinal $k$.\n", "\n", "**Proposition.** On a\n", "\n", "$$\\sum_{\\sigma\\in\\mathfrak S_n}kC_k(\\sigma)=n!$$\n", "\n", "**Démonstration.** Considérons l'ensemble\n", "\n", "$$A=\\{(a,\\sigma):\\sigma\\in\\mathfrak S_n, a\\text{ appartient à une orbite de cardinal }k\\text{ suivant }\\sigma\\}$$\n", "\n", "Soit $\\sigma\\in\\mathfrak S_n$. La permutation $\\sigma$ a $C_k(\\sigma)$ orbites de cardinal $k$, et dans chacune de ces orbites il y a $k$ points. Ainsi,\n", "\n", "$$|A|=\\sum_{\\sigma\\in\\mathfrak S_n}kC_k(\\sigma)$$\n", "\n", "Calculons le cardinal de $A$ d'une autre façon. Soit $a\\in[|0,n-1|]$. Pour créer une permutation pour laquelle $a$ est dans une orbite de cardinal $k$ :\n", "\n", "- On choisit un ensemble $B\\subseteq [|0,n-1|]$ de cardinal $k-1$ (l'orbite sera $B\\cup\\{a\\}$) : $\\binom {n-1}{k-1}$ possibilités. \n", "- On choisit un cycle de longueur $k$ dont le support est $B\\cup\\{a\\}$ : $(k-1)!$ possibilités.\n", "- On choisit une permutation des $n-k$ entiers restants : $(n-k)!$ possibilités.\n", "\n", "Le nombre de permutations pour lesquelles $a$ est dans une orbite de cardinal $k$ est donc\n", "\n", "$$\\binom {n-1}{k-1}(k-1)!(n-k)!=(n-1)!$$\n", "\n", "De là,\n", "\n", "$$|A|=\\sum_{a=0}^{n-1}(n-1)!=n(n-1)!=n!$$\n", "\n", "**Proposition.** Pour tout $k\\in[|1,n|]$, $E(C_k)=\\frac 1 k$.\n", "\n", "**Démonstration.** On a\n", "\n", "$$E(C_k)=\\frac 1{n!}\\sum_{\\sigma\\in\\mathfrak S_n}C_k(\\sigma)=\\frac 1k$$\n", "\n", "Pour $k=1$, nous retrouvons que l'espérance du nombre de points fixes d'une permutation est égal à 1." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Maintenant, quel est le nombre d'orbites d'une permutation $\\sigma\\in\\mathfrak S_n$ ? Notons ce nombre $\\Omega(\\sigma)$. On a évidemment\n", "\n", "$$\\Omega(\\sigma)=\\sum_{k=1}^n C_k(\\sigma)$$\n", "\n", "De là, par la linéarité de l'espérance,\n", "\n", "$$E(\\Omega)=\\sum_{k=1}^n E(C_k)=\\sum_{k=1}^n \\frac 1 k=H_n$$\n", "\n", "où $H_n$ est le $n$ième nombre harmonique." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def H(n):\n", " s = 0\n", " for k in range(1, n + 1):\n", " s += 1 / k\n", " return s" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for n in range(1, 11):\n", " print(n, H(n))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `stats_orbites` renvoie une liste $S$ de longueur $n+1$. Pour $0\\le k\\le n$, $S[k]$ est une estimation de $E(C_k)$. Bien entendu, $S[0]=0$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def stats_orbites(n, N=1000):\n", " S = (n + 1) * [0]\n", " for k in range(N):\n", " s = random_perm(n)\n", " cs = vers_cycles(s)\n", " for c in cs:\n", " l = len(c)\n", " S[l] = S[l] + 1\n", " S[1] += nombre_points_fixes(s)\n", " for k in range(n + 1):\n", " S[k] = S[k] / N\n", " return S" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(stats_orbites(20))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "plt.rcParams['figure.figsize'] = (8, 3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ci-dessous, en noir le nombre « moyen » d'orbites en fonction de $n$. En rouge, la « courbe » de la suite $n\\longmapsto H_n$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ks = range(1, 100, 4)\n", "s = [sum(stats_orbites(k, 1000)) for k in ks]\n", "lg = [H(k) for k in range(1, 100)]\n", "plt.plot(lg, 'r')\n", "plt.plot(ks, s, 'ok', ms=3)\n", "plt.grid()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5. Signature" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La signature de la permutation $\\sigma\\in\\mathfrak S_n$ est $\\varepsilon(\\sigma)=(-1)^{n-m}$ où $m$ est le nombre d'orbites selon $\\sigma$. La fonction $\\varepsilon:\\mathfrak S_n\\longrightarrow\\{-1,1\\}$ est un morphisme de groupes, et elle est facile à calculer pour un cycle." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def signature_cycle(c):\n", " return (-1) ** (len(c) + 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La signature d'une permutation quelconque s'en déduit." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def signature(s):\n", " cs = vers_cycles(s)\n", " p = 1\n", " for c in cs:\n", " p = p * signature_cycle(c)\n", " return p" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = random_perm(20)\n", "print(s)\n", "print(signature(s))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `stats_signature` renvoie une estimation de l'espérance de la signature. Si $n\\ge 2$, la valeur exacte de cette espérance est 0. En effet\n", "\n", "$$E(\\varepsilon)=\\frac 1{n!}\\sum_{\\sigma\\in\\mathfrak S_n}\\varepsilon(\\sigma)=\\frac 1{n!}(|\\mathfrak A_n|-|\\mathfrak S_n\\setminus\\mathfrak A_n|)$$\n", "\n", "où $\\mathfrak A_n$ est l'ensemble des permutations paires. Or,\n", "\n", "$$|\\mathfrak A_n|=|\\mathfrak S_n\\setminus\\mathfrak A_n|=\\frac 1 2 n!$$\n", "\n", "On a donc $E(\\varepsilon)=0$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def stats_signature(n):\n", " N = 1000\n", " av = 0.\n", " for k in range(N):\n", " s = random_perm(n)\n", " av = av + signature(s)\n", " return av / N" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "stats_signature(20)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 6. Ordre d'une permutation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'ordre d'une permutation est le ppcm des ordres des cycles qui la composent. Or, l'ordre d'un cycle est sa longueur." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On commence par définir pgcd et ppcm." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def pgcd(a, b):\n", " while b != 0: a, b = b, a % b\n", " return a" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "pgcd(18, 28)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def ppcm(a, b):\n", " if a == 0 and b == 0: return 0\n", " else:\n", " d = pgcd(a, b)\n", " return (a // d) * b" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ppcm(4, 6)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Maintenant il est facile de calculer l'ordre d'une permutation." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def ordre(s):\n", " cs = vers_cycles(s)\n", " p = 1\n", " for c in cs:\n", " p = ppcm(p, len(c))\n", " return p" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Soyons sans peur, testons sur une permutation $s$ de taille 100000. On calcule l'ordre $\\omega$ de $s$, puis on vérifie que $s^\\omega=id$. Le tout prend moins de 5 secondes sur ma machine (qui n'est pas très rapide). Cela dépend un peu évidemment de la permutation tirée au sort. \n", "\n", "Pour $n = 10^6$, le calcul de l'ordre se fait sur ma machine en 4 ou 5 secondes, la vérification en une trentaine de secondes. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "n = 100000\n", "s = random_perm(n)\n", "o = ordre(s)\n", "print(o)\n", "print(puissance(s, o) == id(n))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Quel est l'ordre moyen $\\mu_n$ d'une permutation de taille $n$ ? Nous admettrons ici que\n", "\n", "$$\\ln \\mu_n\\sim c\\sqrt{\\frac {n}{\\ln n}}$$\n", "\n", "où \n", "\n", "$$c=2\\sqrt{2\\int_0^\\infty\\frac{\\ln(1+t)}{e^t-1}\\, dt}\\simeq 2.99047$$\n", "\n", "L'intégrale apparaissant dans la constante est la **contante de Goh et Schmutz**.\n", "\n", "Juste histoire de vérifier cette valeur, voici une fonction `trapezes`. Elle renvoie une approximation de $\\int_a^bf(x)\\,dx$ par la méthode des trapèzes." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def trapezes(f, a, b, n):\n", " d = (b - a) / n\n", " s = 0\n", " for k in range(n):\n", " s += f(a + k * d)\n", " s += (f(b) - f(a)) / 2\n", " return d * s" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voici la constante de Goh et Schmutz." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "goh_schmutz = trapezes(lambda x:math.log(1 + x) / (math.exp(x) - 1), 0.00001, 100, 10000)\n", "print(goh_schmutz)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et voici une estimation de la constante $c$ ci-dessus." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(2 * math.sqrt(2 * goh_schmutz))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ne soyons pas trop exigeants dans nos tests. Je cite l'article dans lequel j'ai trouvé ce résultat :\n", "\n", "\"__It turns out that a small set of exceptional permutations contributes significantly to the value of $\\mu_n$__\".\n", "\n", "L'article en question est *William M. Y. Goh, Eric Scmutz, The expected Order of a Random Permutation, Bull. London Math. Soc. 23 (1991) 34-42*.\n", "\n", "Cauchemar du statisticien, un petit nombre d'individus domine le groupe. Un calcul sur quelques (milliers de) permutations donnera donc un résultat a priori pas bon." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def stats_ordre(n, N=1000):\n", " av = 0.\n", " for k in range(N):\n", " s = random_perm(n)\n", " av = av + ordre(s)\n", " return av / N" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "mu = stats_ordre(1000)\n", "print(mu)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "n = 1000\n", "c = 2.99047\n", "print(math.log(mu))\n", "print(c * math.sqrt(n / math.log(n)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On s'en contentera :-)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ce n'est évidemment pas la fin de l'histoire, d'autres quantités associées aux permutations se prêtent aussi à des explorations probabilistes très intéressantes (et souvent non triviales)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.8" } }, "nbformat": 4, "nbformat_minor": 2 }