{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ordonner et énumérer les permutations\n",
    "\n",
    "Marc Lorenzi\n",
    "\n",
    "1er avril 2023"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import random\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (8, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'ensemble $\\mathfrak S_n$ des permutations de l'ensemble $[|0,n-1|]$ est un ensemble de cardinal $n!$. Énumérer les permutations de $\\mathfrak S_n$ demande donc un temps au moins de l'ordre de $n!$. Si l'on désire stocker ces permutations, un stockage naïf demandera un espace en $\\mathcal O(n!n)$, puisque chaque permutation nécessite un espace en $\\mathcal O(n)$. Nous allons dans ce notebook décrire un algorithme permettant d'énumérer les permutations mais __sans les stocker__. Plus précisément nous allons définir une relation d'ordre total sur $\\mathfrak S_n$ et un algorithme permmetant, pour chaque permutation $\\sigma\\in \\mathfrak S_n$, de calculer la permutation suivante pour cet ordre à partir de $\\sigma$ seulement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Opérations élémentaires sur les listes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Échanges et comparaisons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous allons dans ce qui suit décrire des algorithmes agissant sur des listes d'entiers. Les opérations que nous allons dénombrer sont :\n",
    "\n",
    "- L'échange de deux éléments d'une liste\n",
    "- La comparaison de deux éléments d'une liste\n",
    "\n",
    "Nous qualifierons ces opérations d'opérations « élémentaires ».\n",
    "\n",
    "Voici les deux fonctions d'échange et de comparaison.\n",
    "\n",
    "- `echanger(s, i, j)` échange $s[i]$ et $s[j]$\n",
    "- `inferieur(s, i, j)` renvoie `True` si $s[i]<s[j]$ et `False` sinon.\n",
    "\n",
    "Remarquez les ligne `cmpt_....incr` dans le code ci-dessous. Ces lignes incrémentent des compteurs (nous en reparlons tout de suite). Les compteurs comptent donc les opérations élémentaires, à condition bien entendu que nous nous obligions à utiliser les fonctions `echanger` et `comparer` pour effectuer ces opérations !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def echanger(s, i, j):\n",
    "    global cmpt_ech\n",
    "    cmpt_ech.incr()\n",
    "    s[i], s[j] = s[j], s[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inferieur(s, i, j):\n",
    "    global cmpt_comp\n",
    "    cmpt_comp.incr()\n",
    "    return s[i] < s[j]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 La classe `Compteur`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici la classe `Compteur`. Elle possède un constructeur qui crée un compteur de valeur initiale 0. Elle possède également une méthode `reset` qui remet le compteur à zéro et une méthode `incr` qui ajoute 1 au compteur. La valeur du compteur est stockée dans son champ `val`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Compteur:\n",
    "    \n",
    "    def __init__(self): self.val = 0\n",
    "    def reset(self): self.val = 0\n",
    "    def incr(self): self.val += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici deux compteurs, appelés `cmpt_ech` et `cmpt_comp`. Comme leur nom l'indique, ils permettront dans la suite de compter des échanges et des comparaisons."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cmpt_ech = Compteur()\n",
    "cmpt_comp = Compteur()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exemple ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(10):\n",
    "    cmpt_ech.incr()\n",
    "print(cmpt_ech.val)\n",
    "cmpt_ech.reset()\n",
    "print(cmpt_ech.val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. L'ordre lexicographique sur $\\mathfrak S_n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Un ordre total sur les permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans tout le notebook $n$ désigne un entier naturel non nul.\n",
    "\n",
    "**Définition.** : Soient $\\sigma, \\sigma'\\in\\mathfrak S_n$. On dit que $\\sigma<\\sigma'$ lorsqu'il existe $k\\in[|0,n-1|]$ tel que \n",
    "- $\\forall i < k$, $\\sigma(i)=\\sigma'(i)$\n",
    "- $\\sigma(k)<\\sigma'(k)$.\n",
    "\n",
    "**Remarque.** Un tel entier $k$ est clairement unique : c'est le plus petit entier tel que $\\sigma(k)\\ne\\sigma'(k)$. \n",
    "\n",
    "__Notation__ : Nous noterons également $\\sigma\\le\\sigma'$ lorsque $\\sigma<\\sigma'$ ou $\\sigma = \\sigma'$. Nous utiliserons également les notations $>$ et $\\ge$ pour désigner les relations inverses de $<$ et $\\le$.\n",
    "\n",
    "**Proposition.** La relation $\\le$ est une relation d'ordre total sur $\\mathfrak S_n$. On l'appelle *l'ordre lexicographique*.\n",
    "\n",
    "**Démonstration**.\n",
    "\n",
    "- Cette relation est clairement réflexive.\n",
    "- Soient $\\sigma, \\sigma'\\in\\mathfrak S_n$. Supposons $\\sigma\\ne\\sigma'$. Soit $k$ le plus petit entier tel que $\\sigma(k)\\ne\\sigma'(k)$. \n",
    "\n",
    "    - Si $\\sigma(k)<\\sigma'(k)$, alors $\\sigma\\le\\sigma'$, et $\\sigma'\\not\\le\\sigma$. \n",
    "    - Sinon, c'est le contraire. Ainsi, la relation est antisymétrique, et totale.\n",
    "\n",
    "- Soient $\\sigma, \\sigma', \\sigma''\\in\\mathfrak S_n$. Supposons $\\sigma\\le\\sigma'$ et $\\sigma'\\le\\sigma''$. Si deux des trois permutations sont égales, on a clairement $\\sigma\\le\\sigma''$. Supposons les maintenant distinctes. Soit $k$ le plus petit entier tel que $\\sigma(k)\\ne\\sigma'(k)$. Soit $\\ell$ le plus petit entier tel que $\\sigma'(\\ell)\\ne\\sigma''(\\ell)$. On distingue ensuite les trois cas $k<\\ell$, $k>\\ell$, $k=\\ell$. On conclut facilement que, dans les trois cas, $\\sigma<\\sigma''$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Permutations et Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $\\sigma\\in\\mathfrak S_n$. Nous modélisons $\\sigma$ en Python par la liste $[\\sigma(0),\\ldots,\\sigma(n-1)]$. L'identité $id$, par exemple, est représentée par la liste $[0,1,\\ldots,n-1]$. \n",
    "\n",
    "**Remarque.** \n",
    "\n",
    "- $id$ est le plus petit élément de $\\mathfrak S_n$ pour l'ordre lexicographique. \n",
    "- Le plus grand élément de $\\mathfrak S_n$ est $\\omega=[n-1,n-2,\\ldots, 0]$. La notation $\\omega$ sera utilisée dans tout le notebook.\n",
    "    \n",
    "Dans toute la suite, nous confondrons les éléments de $\\mathfrak S_n$ et leur représentation en Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def id(n): return list(range(n))\n",
    "def omega(n): return list(range(n - 1, -1, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(id(10))\n",
    "print(omega(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `lexico` renvoie `True` si $s_1\\le s_2$ et `False` sinon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lexico(s1, s2):\n",
    "    n = len(s1)\n",
    "    k = 0\n",
    "    while k < n and s1[k] == s2[k]: k = k + 1\n",
    "    return k == n or s1[k] < s2[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lexico([5, 2, 4, 3, 1, 0], [5, 2, 3, 4, 1, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lexico([5, 2, 3, 4, 1, 0], [5, 2, 4, 3, 1, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Successeur d'une permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Définition.** Soit $(E, \\le)$ un ensemble totalement ordonné. Soit $x\\in E$. On suppose que $x\\ne \\max E$. Soit\n",
    "\n",
    "$$x^+=\\{y\\in E, x<y\\}$$\n",
    "\n",
    "Le *successeur* de $x$ est le plus petit élément de $x^+$, s'il existe.\n",
    "\n",
    "**Lemme.** Tout ensemble totalement ordonné fini non vide possède un plus petit et un plus grand élément.\n",
    "\n",
    "**Démonstration.** Faisons une récurrence sur le cardinal $n$ de l'ensemble $E$. Si $n=1$, c'est évident. Soit donc $n\\ge 1$. Supposons que tout ensemble fini de cardinal $n$ a un plus grand élément. Soit $E$ un ensemble de cardinal $n+1$. Écrivons $E=E'\\cup\\{a\\}$ où $E'$ est de cardinal $n$. Par l'hypothèse de récurrence, $\\max E'=a'$ existe. On vérifie alors aisément que $\\max E$ existe, et est égal au plus grand des deux éléments $a$ et $a'$ (ordre total). L'existence du min se prouve de façon identique.\n",
    "\n",
    "**Proposition.** Soit $E$ un ensemble fini totalement ordonné. Tout élément de $E$ différent de $\\max E$ possède un successeur.\n",
    "\n",
    "**Démonstration.** L'ensemble $x^+$ est\n",
    "\n",
    "- fini car inclus dans $E$, \n",
    "- non vide car $x\\ne\\max E$,\n",
    "- totalement ordonné par l'ordre induit par celui de $E$.\n",
    "\n",
    "Il a donc un plus petit élément."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Revenons à $\\mathfrak S_n$. Prenons par exemple $n=6$. Soit $\\sigma=[2, 3, 5, 4, 1, 0]$. Quel est le successeur de $\\sigma$ ? C'est $[2, 4, 0, 1, 3, 5]$. Comment l'obtient-on ? Voici la recette. Comme vous n'êtes pas en train de lire un livre de cuisine, il s'agira évidemment de prouver la correction de cette recette, mais remettons cela à plus tard.\n",
    "\n",
    "- On commence par trouver le plus long suffixe de $\\sigma$ qui est strictement décroissant. Sur notre exemple, c'est $[5, 4, 1, 0]$. L'indice de 5 dans la permutation $\\sigma$ est 2, nous l'appellerons le __pivot__ de $\\sigma$. Notons-le $i$.\n",
    "\n",
    "- On cherche dans ce suffixe strictement décroissant le plus petit entier strictement supérieur à $\\sigma[i - 1]$, c'est à dire 3 pour notre exemple. Ici, c'est 4. On échange 3 et 4, pour obtenir $\\sigma_1=[2,4,5,3,1,0]$.\n",
    "- On renverse le suffixe de cette permutation commençant à l'indice du pivot (indice 2 ici). On obtient $\\sigma'=[2,4,0,1,3, 5]$, le successeur cherché."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Le code de la fonction `successeur`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Recherche du pivot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `pivot` prend en paramètre une permutation $s$. Elle renvoie, s'il existe, le plus grand entier $i\\ge 1$ tel que $i[k-1]<s[i]$. Un tel entier existe si et seulement si $s\\ne\\omega$. Si $s=\\omega$ la fonction renvoie 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pivot(s):\n",
    "    n = len(s)\n",
    "    i = n - 1\n",
    "    while i > 0 and inferieur(s, i, i - 1): i = i - 1\n",
    "    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(pivot([2, 3, 5, 4, 1, 0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le pivot de $\\omega$ est 0, et c'est la seule permutation à avoir 0 pour pivot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivot(omega(6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le pivot de $id$ est $n-1$. Mais bien d'autres permutations ont $n-1$ pour pivot !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivot(id(6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivot([5, 4, 3, 2, 0, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Recherche de l'élément à échanger avec le pivot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `next_piv` prend en paramètre une permutation $s$. Elle calcule un entier $i$, qui est son pivot. Elle renvoie le couple $(i, j)$ où $j$ est le plus grand entier $j\\ge i$ tel que $s[j]>s[i-1]$. Si $s$ est $\\omega$, le max de $\\mathfrak S_n$, la fonction renvoie le couple $(0,0)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def next_piv(s):\n",
    "    i = pivot(s)\n",
    "    if i > 0:\n",
    "        j = len(s) - 1\n",
    "        while inferieur(s, j, i - 1): \n",
    "            j = j - 1\n",
    "        return (i, j)\n",
    "    else: return (0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next_piv([2, 3, 5, 4, 1, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next_piv(id(6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next_piv(omega(6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next_piv([5, 4, 3, 2, 0, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Renversements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `renverser` renverse la liste $s$ à partir de l'indice $i$. Cette fonction modifie $s$ sur place."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def renverser(s, i):\n",
    "    n = len(s)\n",
    "    j = i\n",
    "    k = n - 1\n",
    "    while j < k:\n",
    "        echanger(s, j, k)\n",
    "        j = j + 1\n",
    "        k = k - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
    "renverser(s, 2)\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 La fonction `successeur`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici la fonction successeur. Elle prend une permutation en paramètre et renvoie la permutation suivante pour l'ordre lexicographique. Si $s=\\omega$, `successeur(s)` renvoie `None`. Remarquez la ligne `s1=s[:]`. On travaille sur une copie de $s$. Il est en effet important pour la suite que $s$ ne soit pas modifiée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def successeur(s):\n",
    "    s1 = s[:]\n",
    "    i, j = next_piv(s1)\n",
    "    if i > 0: \n",
    "        echanger(s1, j, i - 1)\n",
    "        renverser(s1, i)\n",
    "        return s1\n",
    "    else: return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = list(range(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = successeur(s)\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Réévaluez la cellule ci-dessus ... vous verrez apparaître les permutations les unes après les autres dans l'ordre lexicographique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.5 Correction de l'algorithme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La preuve de la correction est truffée de cas. En voici une ébauche, la fin de la preuve étant laissée au lecteur.\n",
    "\n",
    "Soit $\\sigma\\in\\mathcal S_n\\setminus\\{\\omega\\}$. Soit $\\sigma'$ définie par l'algorithme. Soit $i\\ge 1$ le pivot de $\\sigma$. Nous avons donc $\\sigma'(\\ell)=\\sigma(\\ell)$ pour $\\ell=0,\\ldots,i-2$.\n",
    "\n",
    "Soit $\\gamma>\\sigma$. Il existe donc $k\\in[0,n-1]$ tel que\n",
    "\n",
    "- $\\gamma(\\ell) =\\sigma(\\ell)$ pour $\\ell=0,\\ldots,k-1$.\n",
    "- $\\gamma(k) > \\sigma(k)$.\n",
    "\n",
    "Discutons suivant la position de $k$ par rapport à $i-1$.\n",
    "\n",
    "- Si $k < i-1$, alors $\\gamma>\\sigma'$ puisque $\\sigma'$ et $\\sigma$ coïncident sur $[0,k]$.\n",
    "- $k> i-1$ est impossible. On aurait en effet dans ce cas que $\\sigma$ et $\\gamma$ coïncident sur $[0,k-1]$. $\\gamma(k)=\\sigma(k')$ pour un entier $k'>k$, mais la suite $(\\sigma(k),\\ldots,\\sigma(n-1))$ est strictement décroissante. On aurait donc $\\gamma(k) < \\sigma(k)$, ce qui ne'est pas.\n",
    "- Regardons enfin le cas où $k=i-1$. Soit $j$ le plus grand indice, $j\\ge i$ tel que $\\sigma(j)>\\sigma(i)$. Par la décroissance de $\\sigma$ à partir de l'indice $i$, on a $\\gamma(k)=\\sigma(i),\\sigma(i+1),\\ldots,$ ou $\\sigma(j)$, puisque les valeurs suivantes sont strictement inférieures à $\\sigma(i-1)$. Si $\\gamma(k)\\ne\\sigma(j)$, alors, comme $\\sigma'(i-1)=\\sigma(j)$, on a $\\gamma>\\sigma$. Supposons donc $\\gamma(k)=\\sigma(j)$. $\\gamma$ et $\\sigma'$ coïncident sur $[0,i-1]$. Soit $\\ell$ le premier indice en lequel $\\gamma$ et $\\sigma'$ ne coïncident pas. On laisse au lecteur le soin de terminer la démonstration. Considérer les cas $\\ell<j$, $\\ell>j$ et $\\ell=j$. Dans les deux premiers cas on conclut que $\\gamma > \\sigma'$. Dans le troisième cas il faut encore discuter et on trouve que $\\gamma\\ge \\sigma'$. \n",
    "\n",
    "En résumé, pour tout $\\gamma\\in\\mathfrak S_n$, si $\\gamma>\\sigma$ alors $\\gamma\\ge \\sigma'$. La permutation $\\sigma'$ est bien le successeur de $\\sigma$ dans $\\mathfrak S_n$ pour l'ordre lexicographique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Énumérer les permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 Le code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `permutations` ci-dessous énumère les permutations de $\\mathfrak S_n$ dans l'ordre lexicographique à partir de $id$, à cela près qu'à chaque itération un appel à `yield` est effectué. Explications à suivre ...  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def permutations(n):\n",
    "    s = list(range(n))\n",
    "    while True:\n",
    "        yield s\n",
    "        s = successeur(s)\n",
    "        if s == None: break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un petit test ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "permutations(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Euh, oui, bon, et alors ? Un second test ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "permutations(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Générateurs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Là on n'y croit plus du tout. Le cardinal de $\\mathfrak S_{1000}$ est largement supérieur au nombre d'atomes dans l'univers. Mais alors, que fait la fonction `permutations` ? Elle renvoie un *générateur*. Exemple de création d'un générateur en Python ? La fonction `range`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "range(10 ** 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A-t-on créé un objet avec $10^{10}$ entiers dedans ? Pas du tout. Mais si on applique certaines fonctions comme `list`  à cet objet, ou que l'on écrit une ligne du genre `for i in range(10 ** 10):`, il va *engendrer* tous les entiers de 0 à $10^{10}-1$.\n",
    "\n",
    "Il en va de même pour notre fonction `permutations` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for s in permutations(4):\n",
    "    print(s, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remarquons que le cardinal de $\\mathfrak S_n$ est $n!$. Demander *toutes* les permutations prend donc un temps au minimum « factoriel ». Alors soyons modestes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "len(list(permutations(9)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un appel à `list(permutations(10))` prendrait au moins 10 fois plus de temps. Et si l'on met 11 au lieu de 9, au moins 110 fois plus de temps ! Ce temps prohibitif n'est pas dû au fait que notre fonction `successeur` est mauvaise, mais au fait que le nombre d'objets à calculer est lui-même prohibitif. En fait nous allons voir que `successeur` est une TRÈS bonne fonction. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. La complexité de la fonction `permutations`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 Meilleur cas et pire cas de la fonction `successeur`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $s\\in\\mathfrak S_n$, $s\\ne\\omega$. \n",
    "\n",
    "- Soit $i$ le pivot de $s$. La recherche de $i$ nécessite $n-i$ comparaisons.\n",
    "- La recherche du $j$ maximal tel que $i\\le j$ et $s[i-1]<s[j]$ nécessite $n-j$ comparaisons.\n",
    "- L'échange de $s[i-1]$ et $s[j]$ nécessite ... 1 échange.\n",
    "- Le renversement de la queue de liste nécessite $\\lfloor\\frac{n-i}{2}\\rfloor$ échanges.\n",
    "\n",
    "Nous avons donc au total $2n - i - j$ comparaisons et $\\lfloor\\frac{n-i}{2}\\rfloor + 1$ échanges.\n",
    "\n",
    "Si $i=n-1$, alors $j$ aussi et il y a 2 comparaisons et 1 échange, qui sont clairement minimaux.\n",
    "\n",
    "Comme $s\\ne \\omega$, on a $i\\ge 1$. Le pire cas survient lorsque $i=j=1$, auquel cas il y a $2n-2$ comparaisons et $\\lfloor\\frac{n-1}{2}\\rfloor + 1=\\lfloor\\frac{n+1}{2}\\rfloor$ échanges."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La complexité de la fonction `successeur` est donc $\\mathcal O(1)$ en meilleur cas et $\\mathcal O(n)$ en pire cas (en termes d'échanges et/ou de comparaisons).\n",
    "\n",
    "La complexité de la fonction `permutations` est ainsi $\\mathcal O(n!n)$ puisqu'il y a $n!$ appels à la fonction successeur. \n",
    "\n",
    "Nous allons maintenant montrer qu'on peut dire beaucoup mieux que cela."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 Nombre d'échanges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Proposition.** la complexité de `permutations` en nombre d'échanges est équivalente, lorsque $n$ tend vers l'infini, à \n",
    "\n",
    "$$n!\\cosh 1$$\n",
    "\n",
    "**Démonstration.** Notons $I_n$ le nombre d'échanges d'éléments de liste effectués lors de l'appel `permutations(n)`. On a $I_1=0$ et, pour tout $n\\ge 2$, \n",
    "\n",
    "$$I_n=nI_{n-1}+(n-1)\\left\\lfloor\\frac{n+1}2\\right\\rfloor$$\n",
    "\n",
    "En effet :\n",
    "\n",
    "- Pour $k=0,\\ldots,n-1$, la fonction énumère les permutations $s$ telles que $s[0]=k$, ce qui demande, pour chaque valeur de $k$, $I_{n-1}$ échanges.\n",
    "- Pour $k=0,\\ldots,n-2$, la fonction calcule le successeur de la plus grande permutation $s$ telle que $s[0]=k$. Cette permutation est $s=[k,n-1,n-2,\\ldots,0]$  (où $k$ n'apparaît pas dans les pointillés). Le pivot de $s$ est $i=1$, Le renversement nécessite donc $\\left\\lfloor\\frac{n-1}2\\right\\rfloor$, et passer de $s$ à son successeur nécessite ainsi $\\left\\lfloor\\frac{n+1}2\\right\\rfloor$ échanges.\n",
    "- Pour $k=n-1$, le calcul du successeur de $\\omega$ (enfin, plutôt l'échec de ce calcul) ne nécessite aucun échange."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une petite vérification s'impose."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_echanges0(n):\n",
    "    if n == 1: return 0\n",
    "    else:\n",
    "        return n * nombre_echanges0(n - 1) + (n - 1) * ((n + 1) // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 6\n",
    "cmpt_ech.reset()\n",
    "s = list(permutations(n))\n",
    "print(cmpt_ech.val)\n",
    "print(nombre_echanges0(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tout va pour le mieux. Attaquons nous au calcul explicite de $I_n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Posons\n",
    "\n",
    "$$S_n=I_n+\\left\\lfloor\\frac{n+1}2\\right\\rfloor$$\n",
    "\n",
    "On laisse au lecteur le soin de vérifier que $S_1=1$ et, pour tout $n\\ge 2$, \n",
    "\n",
    "$$S_n=n(S_{n-1}+\\varepsilon_{n-1})$$\n",
    "\n",
    "où $\\varepsilon_n=0$ si $n$ est impair et 1 si $n$ est pair. On montre alors facilement par récurrence sur $n$ que\n",
    "\n",
    "$$S_n=n!\\left(1+\\frac{1}{2!}+\\frac{1}{4!}+\\frac{1}{6!}+\\ldots+\\frac{1}{2\\lfloor(n-1)/2\\rfloor}\\right)$$\n",
    "\n",
    "d'où\n",
    "\n",
    "$$I_n=n!\\sum_{j=0}^{\\left\\lfloor\\frac{n-1}2\\right\\rfloor}\\frac 1 {(2j)!}-\\left\\lfloor\\frac{n+1}2\\right\\rfloor$$\n",
    "\n",
    "Remarquons que $\\sum_{j=0}^{\\left\\lfloor\\frac{n-1}2\\right\\rfloor}\\frac 1 {(2j)!}$ est une somme partielle de série, qui tend, lorsque $n$ tend vers l'infini, vers\n",
    "\n",
    "$$\\sum_{j=0}^{\\infty}\\frac 1 {(2j)!}=\\cosh 1\\simeq 1.54308$$\n",
    "\n",
    "Ainsi,\n",
    "\n",
    "$$I_n\\sim n!\\cosh 1$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "math.cosh(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons tout cela."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_echanges(n):\n",
    "    p = (n + 1) // 2\n",
    "    s = 0\n",
    "    for j in range(p):\n",
    "        s += 1 / math.factorial(2 * j)\n",
    "    return math.factorial(n) * s - p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 6\n",
    "cmpt_ech.reset()\n",
    "s = list(permutations(n))\n",
    "print(cmpt_ech.val)\n",
    "print(nombre_echanges(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pas d'erreur, notre formule pour $I_n$ donne bien la valeur exacte du nombre d'échanges. Voici le graphe de la complexité de `permutations(n)` divisé par $n!$ en fonction de $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cmpts = []\n",
    "for k in range(1, 10):\n",
    "    cmpt_ech.reset()\n",
    "    s = list(permutations(k))\n",
    "    cmpts.append(cmpt_ech.val / math.factorial(k))\n",
    "plt.plot(range(1, 10), cmpts, 'k')\n",
    "plt.plot(range(1, 10), cmpts, 'or')\n",
    "plt.grid()   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 Nombre de comparaisons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Proposition.** la complexité de `permutations` en nombre de comparaisons d'éléments de listes est équivalente, lorsque $n$ tend vers l'infini, à\n",
    "\n",
    "$$\\left(\\frac {3e} 2 -1\\right)n!$$\n",
    "\n",
    "**Démonstration.** Notons $C'_n$ le nombre de comparaisons d'éléments de liste effectués lors de l'appel `permutations(n)`, en excluant le calcul (qui échoue) du successeur de $\\omega$. On a $C'_1=0$ et, pour tout $n\\ge 2$, \n",
    "\n",
    "$$C'_n=nC'_{n-1}+\\frac 1 2 (n-1)(3n-2)$$\n",
    "\n",
    "En effet :\n",
    "\n",
    "- Pour $k=0,\\ldots,n-1$, la fonction énumère les permutations $s$ telles que $s[0]=k$, ce qui demande, pour chaque valeur de $k$, $C_{n-1}$ comparaisons.\n",
    "- Pour $k=0,\\ldots,n-2$, la fonction calcule le successeur de la plus grande permutation $s$ telle que $s[0]=k$. Cette permutation est $s=[k,n-1,n-2,\\ldots,0]$ (où $k$ n'apparaît pas dans les pointillés). Le pivot de $s$ est $i=1$. Passer de $s$ à son successeur demande donc\n",
    "    - $n-1$ comparaisons pour trouver le pivot, égal à 1.\n",
    "    - $k+1$ comparaisons pour trouver l'indice $j$ maximal tel que $s[j]>s[0]$.\n",
    "Au total, cela donne\n",
    "\n",
    "$$n(n-1)+\\sum_{k=0}^{n-2}k=n(n-1)+\\frac 1 2 (n-2)(n-1)=\\frac 1 2 (n-1)(3n-2)$$\n",
    "\n",
    "Remarquons que le calcul du successeur de $\\omega$, quant à lui, nécessite $n-1$ comparaisons.\n",
    "\n",
    "Avant de calculer $C'_n$ en fonction de $n$, testons notre récurrence !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_comparaisons0(n):\n",
    "    if n == 1: return 0\n",
    "    else:\n",
    "        return n * nombre_comparaisons0(n - 1) + (n - 1) * (3 * n - 2) / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 8\n",
    "cmpt_comp.reset()\n",
    "list(permutations(n))\n",
    "print(cmpt_comp.val)\n",
    "print(nombre_comparaisons0(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un écart de 7 entre le nombre de comparaisons donné par la récurrence et le nombre de comparaisons réel. Normal, il manque les comparaisons effectuées lors du calcul du successeur (inexistant) de $\\omega$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Posons maintenant\n",
    "\n",
    "$$T_n=C'_n+\\frac 1 2(3n+1)$$\n",
    "\n",
    "On obtient facilement que $T_1=2$, et pour tout $n\\ge 2$,\n",
    "\n",
    "$$T_n= nT_{n-1}+1$$\n",
    "\n",
    "On montre alors par récurrence sur $n$ que pour tout $n\\ge 1$,\n",
    "\n",
    "$$T_n=n!\\left(\\frac 3 2\\sum_{k=0}^n\\frac 1 {k!}-1\\right)$$\n",
    "\n",
    "et donc\n",
    "\n",
    "$$C'_n=n!\\left(\\frac 3 2\\sum_{k=0}^n\\frac 1 {k!}-1\\right)-\\frac 1 2(3n+1)$$\n",
    "\n",
    "Il reste à ajouter le nombre de comparaisons effectuées par le calcul (qui échoue) du successeur de $\\omega$. Ces comparaisons se font lors de la recherche du pivot, il en a $n-1$. Pour ceux qui cherchent la petite bête, il y en a $n-1$ et pas $n$ parce que, dans le code de la fonction `pivot`, le test `k>0` de la ligne `while k > 0 and inferieur(s, k, k - 1):` échoue lorsque $k=0$ et, donc, le second test `inferieur(s, k, k - 1)` n'est pas exécuté dans ce cas.\n",
    "\n",
    "Le nombre de comparaisons effectuées par `permutations`, que nous appellerons $C_n$, est donc\n",
    "\n",
    "$$C_n=n!\\left(\\frac 3 2\\sum_{k=0}^n\\frac 1 {k!}-1\\right)-\\frac 1 2(n+3)$$\n",
    "\n",
    "La quantité entre parenthèses tend vers $\\frac 3 2 e - 1\\simeq 3.07742$ lorsque $n$ tend vers l'infini. Ainsi,\n",
    "\n",
    "$$C_n\\sim\\left(\\frac {3e} 2 - 1\\right)n!$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Illustrons tout cela avec un peu de code, comme nous l'avons fait pour le nombre d'échanges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_comparaisons(n):\n",
    "    s = 0\n",
    "    for k in range(n + 1):\n",
    "        s = s + 1 / math.factorial(k)\n",
    "    s = 3 / 2 * s - 1\n",
    "    return math.factorial(n) * s - (n + 3) / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 8\n",
    "cmpt_comp.reset()\n",
    "list(permutations(n))\n",
    "print(cmpt_comp.val)\n",
    "print(nombre_comparaisons(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cmpts = []\n",
    "for k in range(1, 10):\n",
    "    cmpt_comp.reset()\n",
    "    s = list(permutations(k))\n",
    "    cmpts.append(cmpt_comp.val / math.factorial(k))\n",
    "plt.plot(range(1, 10), cmpts, 'k')\n",
    "plt.plot(range(1, 10), cmpts, 'or')\n",
    "plt.grid()   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 La complexité en moyenne de `successeur`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les deux paragraphes précédents nous montrent que les $n!$ appels à la fonction `successeur` pour les permutations de $\\mathfrak S_n$ nécessitent un nombre total d'opérations élémentaires (comparaisons et échanges) équivalent à\n",
    "\n",
    "$$I_n+C_n\\sim\\left(\\cosh 1 + \\frac {3e} 2 - 1\\right)n!$$\n",
    "\n",
    "En munissant $\\mathfrak S_n$ de la probabilité uniforme, la complexité moyenne de la fonction `successeur` est\n",
    "\n",
    "$$\\frac{I_n+C_n}{n!}\\sim\\mu$$\n",
    "\n",
    "où\n",
    "\n",
    "$$\\mu=\\left(\\cosh 1 + \\frac {3e} 2 - 1\\right)=2e+\\frac 1 {2e} - 1\\simeq 4.6205$$\n",
    "\n",
    "c'est à dire une complexité ... en $\\mathcal O(1)$ ! Ci-dessous, le graphe de cette complexité moyenne."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(2 * math.e + 1 / (2 * math.e) - 1 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cmpts = []\n",
    "for k in range(1, 10):\n",
    "    cmpt_comp.reset()\n",
    "    cmpt_ech.reset()\n",
    "    s = list(permutations(k))\n",
    "    cmpts.append((cmpt_comp.val + cmpt_ech.val) / math.factorial(k))\n",
    "plt.plot(range(1, 10), cmpts, 'k')\n",
    "plt.plot(range(1, 10), cmpts, 'or')\n",
    "plt.grid()   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(cmpts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Pour terminer, faisons quelques statistiques, histoire de voir que notre belle théorie fonctionne parfaitement en pratique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.4 Statistiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `random_perm` ci-dessous renvoie une permutation aléatoire des entiers entre 0 et $n-1$. Elle utilise *l'algorithme de Fisher-Yates*, que nous ne détaillerons pas ici."
   ]
  },
  {
   "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": [
    "random_perm(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Proposition.** Pour toute permutation $\\sigma\\in\\mathfrak S_n$, la fonction `random_perm` renvoie $\\sigma$ avec une probabilité $\\frac 1 {n!}$.\n",
    "\n",
    "**Démonstration.** admise."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonctions `test_succ` tire $N$ permutations aléatoires et calcule leur successeur. Elle renvoie la moyenne du nombre d'opérations élémentaires effectuées. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_succ(n, N=50000):\n",
    "    count = 0\n",
    "    for k in range(N):\n",
    "        cmpt_comp.reset()\n",
    "        cmpt_ech.reset()\n",
    "        s = random_perm(n)\n",
    "        s1 = successeur(s)\n",
    "        count += cmpt_comp.val + cmpt_ech.val\n",
    "    return count / N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_succ(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rappelons que la théorie prévoit une moyenne d'environ $4.62$. Eh bien la théorie fait une bonne prévision :-).\n",
    "\n",
    "Quelle est la __loi__ de la variable aléatoire « nombre d'opérations » ? Nous ne ferons pas de théorie ici, contentons nous d'un histogramme. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def histo_succ(n, N=10000):\n",
    "    p = (5 * n) // 2\n",
    "    histo = p * [0]\n",
    "    for k in range(N):\n",
    "        cmpt_comp.reset()\n",
    "        cmpt_ech.reset()\n",
    "        s = random_perm(n)\n",
    "        s1 = successeur(s)\n",
    "        count = cmpt_comp.val + cmpt_ech.val\n",
    "        histo[count] += 1\n",
    "    for k in range(p):\n",
    "        histo[k] = histo[k] / N\n",
    "    return histo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = histo_succ(10)\n",
    "plt.plot(h, 'k')\n",
    "plt.plot(h, 'or')\n",
    "plt.grid()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une dernière petite remarque avant de clore ce notebook. Apparemment, la probabilité que le nombre d'opérations élémentaires soit égal à 3 est $\\frac 1 2$. Comment cela se fait-il ?\n",
    "\n",
    "Soit $n\\ge 3$. Soit $s\\in\\mathfrak S_n$. Supposons que le pivot de $s$ ne soit pas $n-1$. Soit $s'$ le successeur de $s$. On a $s[n-2]>s[n-1]$ et donc (voir la fonction `successeur`), $s'[n-2]<s'[n-1]$. Ainsi, le pivot de $s'$ est $n-1$, et donc la complexité de `successeur` pour le calcul de $s''$, successeur de $s'$, est 3. De plus (exercice), le pivot de $s''$ n'est pas $n-1$. Comme le pivot de $id$ est $1\\ne n-1$, exactement la moitié des permutations ont un pivot $i$ égal à $n-1$, donc \n",
    "\n",
    "$$\\mathbb P(i=n-1)=\\frac 1 2$$"
   ]
  }
 ],
 "metadata": {
  "kernel_info": {
   "name": "python3"
  },
  "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"
  },
  "nteract": {
   "version": "0.14.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}