{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0b5c3b6a",
   "metadata": {},
   "source": [
    "# Permanent\n",
    "\n",
    "Marc Lorenzi\n",
    "\n",
    "10 mars 2023"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1f701382",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import random\n",
    "import time\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6db8545",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (8, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d1a4bb7",
   "metadata": {},
   "source": [
    "**Notations et conventions.** $\\mathbb K$ désigne un corps quelconque. Pour toute matrice $A\\in\\mathcal M_n(\\mathbb K)$, nous ferons varier les indices des lignes et colonnes de $A$ entre 0 et $n-1$, plutôt qu'entre 1 et $n$.\n",
    "\n",
    "Pour tout $n\\in\\mathbb N$, nous noterons $\\bar n=[\\!|0,n-1|\\!]$ et $\\mathfrak S_n=\\mathfrak S(\\bar n)$ l'ensemble des bijections de l'ensemble $\\bar n$ sur lui-même. Rappelons que le cardinal de $\\mathfrak S_n$ est $n!$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "514d5eb2",
   "metadata": {},
   "source": [
    "## 1. Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78725cd9",
   "metadata": {},
   "source": [
    "### 1.1 Mariages parfaits"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17fde4dc",
   "metadata": {},
   "source": [
    "$n$ cours sont à répartir dans $n$ salles de classe. Certaines contraintes (nombre d'étudiants, équipements) font qu'un cours ne peut avoir lieu que dans certaines salles. Il s'agit d'affecter une salle à chacun des cours. Quelques problèmes se posent d'emblée :\n",
    "\n",
    "1. Étant donnée une affectation de salles, vérifier que c'est bien une solution.\n",
    "2. Y a-t-il une solution ?\n",
    "3. Trouver une solution, s'il y en a une.\n",
    "3. Trouver toutes les solutions.\n",
    "4. Combien y a-t-il de solutions ?\n",
    "\n",
    "Les trois premiers problèmes peuvent être résolus en temps polynomial. C'est clair pour le problème numéro 1, beaucoup moins évident pour les problèmes 2 et 3. Ce qui va nous intéresser ici c'est la résolution du dernier problème : combien y a-t-il de solutions ? Nous reviendrons sur les problèmes numéros 3 et 4, de façon très naïve, tout à la fin du notebook.\n",
    "\n",
    "Pour mathématiser le problème, donnons-nous un *graphe bipartite* $G$ possédant $2n$ sommets. Qu'est-ce qu'un graphe bipartite, me direz-vous ? Et qu'est-ce qu'un graphe ?\n",
    "\n",
    "**Définition.** Un *graphe* (orienté) est un couple $G=(S, A)$ où $S$ est un ensemble fini, l'ensemble des *sommets* de $G$ et $A\\subseteq S\\times S$ est l'ensemble des *arêtes* de $G$. Si $a=(x,y)\\in A$, $x$ est *l'origine* de $a$ et $y$ est la *destination* de $a$. Les sommets $x$ et $y$ sont les *extrémités$ de $a$. Dans le cas où $x=y$, l'arête $a$ est une *boucle* sur le sommet $x$.\n",
    "\n",
    "**Définition.** Soit $G=(S,A)$ un graphe. Le graphe $G$ est *bipartite* (non orienté) s'il existe une partition $S=X\\cup Y$ de l'ensemble $S$ des sommets de $G$ telle que $A\\subseteq (X\\times Y)\\cup(Y\\times X)$ et pour tous $x,y\\in S$, $(x,y)\\in A\\iff (y,x)\\in A$.\n",
    "\n",
    "Donnons-nous un graphe bipartite $G$. Nous supposerons de plus, dans ce qui va suivre, que $|X|=|Y|$, où la double barre désigne le cardinal de l'ensemble (le cardinal de $S$ est donc pair).\n",
    "\n",
    "Écrivons $S=X\\cup Y$ où $X=\\{x_0,\\ldots,x_{n-1}\\}$ et $Y=\\{y_0,\\ldots,y_{n-1}\\}$. Notre problème est maintenant le suivant :\n",
    "\n",
    "Combien y a-t-il de *mariages parfaits* du graphe $G$, c'est à dire de permutations $\\sigma\\in\\mathfrak S_n$ telles que pour tout $i\\in\\bar n$, il y a une arête de $G$ d'extrémités $x_i$ et $y_{\\sigma(i)}$ ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2aa61828",
   "metadata": {},
   "source": [
    "Pour illustrer un peu tout cela, voici une fonction `graphe_bipartite_alea` qui prend en paramètre un entier $n$. Elle renvoie un graphe bipartite $G$ « aléatoire » (enfin pas tout à fait, lisez le code) ayant $2n$ sommets. Le graphe $G$ est modélisé par une liste de longueur $n$. Pour $i\\in\\bar n$, $G[i]$ est une liste d'entiers entre 0 et $n-1$. L'entier $j$ est dans $G[i]$ si et seulement si il existe une arête d'extrémités $x_i$ et $y_j$.\n",
    "\n",
    "La fonction accepte un paramètre facultatif $r\\in[0,1]$. Plus $r$ est grand, plus $G$ possède d'arêtes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52126598",
   "metadata": {},
   "outputs": [],
   "source": [
    "def graphe_bipartite_alea(n, r=0.3):\n",
    "    G = n * [None]\n",
    "    for i in range(n): G[i] = []\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            p = random.uniform(0, 1)\n",
    "            if p < r: G[i].append(j)\n",
    "    for i in range(n):\n",
    "        if G[i] == []:\n",
    "            j = random.randint(0, n - 1)\n",
    "            G[i].append(j)\n",
    "    return G"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "542a7565",
   "metadata": {},
   "source": [
    "Voici une fonction `plot_graph` qui affiche un graphe bipartite. En noir, l'ensemble $X$ des $x_i$, en rouge l'ensemble $Y$ des $y_j$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "77755559",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_graph(G):\n",
    "    n = len(G)\n",
    "    xs = list(range(n))\n",
    "    for i in range(n):\n",
    "        for j in G[i]: plt.plot([i, j], [0, 1], 'k')\n",
    "    plt.plot(xs, n * [1], 'or', ms=10)\n",
    "    plt.plot(xs, n * [0], 'ok', ms=10)\n",
    "    plt.axis('off')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6101d72c",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_graph(graphe_bipartite_alea(10, r=0.2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cea01650",
   "metadata": {},
   "source": [
    "Considérons la matrice $A^G\\in\\mathcal M_n(\\{0,1\\})$ définie, pour tous $i,j\\in\\bar n$, par $A^G_{ij}=1$ s'il existe dans le graphe $G$ une arête d'extrémités $x_i$ et $y_j$ et $A^G_{ij}=0$ sinon. Cette matrice s'appelle la *matrice de biadjacence* de $G$.\n",
    "\n",
    "Soit $\\sigma\\in\\mathfrak S_n$. La permutation $\\sigma$ est un mariage parfait du graphe $G$ si et seulement si pour tout $i\\in\\bar n$, $A^G_{i\\sigma(i)}=1$, c'est à dire $A^G_{0\\sigma(0)}\\ldots A^G_{(n-1)\\sigma(n-1)}=1$. Sinon, ce produit vaut 0. Ainsi, le nombre de mariages parfaits de $G$ est\n",
    "\n",
    "$$\\sum_{\\sigma\\in\\mathfrak S_n}\\prod_{0\\le i < n}A^G_{i\\sigma(i)}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a20d5cce",
   "metadata": {},
   "source": [
    "La fonction `matrice_biadjacence` prend en paramètre un graphe bipartite $G$ et renvoie la matrice $A^G$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "134b3729",
   "metadata": {},
   "outputs": [],
   "source": [
    "def matrice_biadjacence(G):\n",
    "    n = len(G)\n",
    "    A = n * [None]\n",
    "    for i in range(n):\n",
    "        A[i] = n * [0]\n",
    "    for i in range(n):\n",
    "        for j in G[i]:\n",
    "            A[i][j] = 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bfd4a3a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = graphe_bipartite_alea(5)\n",
    "A = matrice_biadjacence(G)\n",
    "for i in range(5): print(A[i])\n",
    "plot_graph(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bed63c76",
   "metadata": {},
   "source": [
    "Venons-en à ce qui nous intéresse. Nous reviendrons sur les mariages parfaits à la fin du notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37bc81ec",
   "metadata": {},
   "source": [
    "### 1.2 Notion de permanent"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "255b8af1",
   "metadata": {},
   "source": [
    "**Définition.** Soit $A\\in\\mathcal M_n(\\mathbb K)$. Le *permanent* de la matrice $A$ est\n",
    "\n",
    "$$\\text{perm}(A)=\\sum_{\\sigma\\in\\mathfrak S_n}\\prod_{0\\le i<n}A_{i\\sigma(i)}$$\n",
    "\n",
    "L'expression du permanent d'une matrice ressemble beaucoup à celle de son déterminant :\n",
    "\n",
    "$$\\det(A)=\\sum_{\\sigma\\in\\mathfrak S_n}\\varepsilon(\\sigma)\\prod_{0\\le i<n}A_{i\\sigma(i)}$$\n",
    "\n",
    "où $\\varepsilon(\\sigma)$ est la *signature* de la permutation $\\sigma$. Cependant, alors qu'il existe des algorithmes efficaces (le pivot de Gauss, par exemple) pour calculer un déterminant, on n'en connaît à ce jour aucun pour calculer un permanent. Pour dire les choses très vite (et donc faussement), on dit qu'une fonction est dans la classe $\\#P$ lorsqu'elle est calculable en espace polynomial. Le calcul du permanent est un *problème $\\#P$-difficile*. Si l'on connaissait un algorithme en temps polynomial pour calculer un permanent, alors toutes les fonctions de la classe $\\#P$ pourraient être calculées en temps polynomial. C'est le *théorème de Valiant*. On peut montrer que cela permettrait entre autres de répondre par l'affirmative à l'un des problèmes d'informatique théorique réputés les plus inabordables à ce jour, à savoir que $P=NP$. Autant dire que nous allons faire ce que nous pouvons pour calculer des permanents mais qu'il ne faut pas s'attendre à des miracles. D'ici la fin du notebook, nous serons en mesure de calculer le permanent d'une matrice de taille 20, mais pas vraiment plus."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d6dc7f1",
   "metadata": {},
   "source": [
    "Nous allons dans ce qui suit décrire trois algorithmes de calcul du permanent.\n",
    "\n",
    "- L'algorihme naïf, qui repose sur la définition du permanent.\n",
    "- La formule de Laplace, qui est l'analogue pour les permanents de la formule de développement d'un déterminant par rapport à une ligne ou une colonne.\n",
    "- La formule de Ryser, plus efficace que la formule de Lagrange.\n",
    "\n",
    "La formule de Ryser est l'un des meilleurs algorithmes actuellement connus pour calculer la valeur exacte d'un permanent."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8fe61b49",
   "metadata": {},
   "source": [
    "### 1.3 Quelques fonctions Python utiles"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9511cd85",
   "metadata": {},
   "source": [
    "Passons rapidement sur quelques fonctions Python qui nous serons bien utiles."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71509499",
   "metadata": {},
   "source": [
    "La fonction `taille` prend en paramètre une matrice carrée, représentée en Python par une liste de listes. Elle renvoie la taille de la matrice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5143b4fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "def taille(A): return len(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7e9a2bb",
   "metadata": {},
   "source": [
    "La fonction `matrice` renvoie une matrice de taille $n$ dont tous les coefficients sont égaux à $x$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "08cfe9fc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def matrice(n, x):\n",
    "    A = n * [None]\n",
    "    for i in range(n):\n",
    "        A[i] = n * [x]\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a4ad14de",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(matrice(3, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "249f3024",
   "metadata": {},
   "source": [
    "La fonction `print_mat` afiche joliment une matrice. Le paramètre optionnel $\\ell$ définit la largeur d'affichage des coefficients. La valeur par défaut 2 convient si les les coefficients de $A$ sont des entiers de 1 chiffre avec un éventuel signe moins."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "04f3c105",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_mat(A, l=2):\n",
    "    n = taille(A)\n",
    "    s = ''\n",
    "    for i in range(n):\n",
    "        s += n * ('+' + (l + 2) * '-') + '+\\n'\n",
    "        for j in range(n):\n",
    "            s += ('| %' + str(l) + 's ') % A[i][j]\n",
    "        s += '|\\n'\n",
    "    s += n * ('+' + (l + 2) * '-') + '+'\n",
    "    print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "32c233e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "print_mat(matrice(3, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04907d3d",
   "metadata": {},
   "source": [
    "La fonction `randmat` renvoie une matrice de taille $n$ dont les coefficients sont des entiers aléatoires entre $a$ et $b$ inclus (par défaut, entre $-9$ et $9$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f6084c4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def randmat(n, a=-9, b=9):\n",
    "    A = matrice(n, 0)\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            A[i][j] = random.randint(a, b)\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9c7994a",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(5)\n",
    "print_mat(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a06e3f3",
   "metadata": {},
   "source": [
    "### 1.4 Un calcul naïf du permanent"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "004d86e3",
   "metadata": {},
   "source": [
    "Commençons par écrire une fonction qui énumère toutes les permutations d'un ensemble $E$. Plus exactement, $E$ est donné par la liste de ses éléments et la fonction énumère toutes les permutations de cette liste. Le code ci-dessous est très naïf (on peut faire mieux que cela) :\n",
    "\n",
    "- Si $E$ est vide il n'y a qu'une permutation de $E$, à savoir $[]$.\n",
    "- Sinon, soit $a$ un élément de $E$. Pour chaque permutation $\\sigma$ de $E\\setminus\\{a\\}$, on énumère les permutations obtenues en insérant $a$ dans $\\sigma$.\n",
    "\n",
    "Cette fonction est en fait ce que Python appelle un *générateur*. Elle ne crée pas la *liste* des permutations, elle les *énumère*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "363f0d10",
   "metadata": {},
   "outputs": [],
   "source": [
    "def permutations(E):\n",
    "    if E == []: yield []\n",
    "    else:\n",
    "        n = len(E)\n",
    "        a = E[0]\n",
    "        P1 = permutations(E[1:])\n",
    "        P = []\n",
    "        for sigma in P1:\n",
    "            for k in range(n):\n",
    "                yield sigma[:k] + [a] + sigma[k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "82526323",
   "metadata": {},
   "outputs": [],
   "source": [
    "for sigma in permutations([1, 2, 3]): print(sigma)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4231901",
   "metadata": {},
   "source": [
    "Le calcul naïf du permanent d'une matrice $A$ est maintenant immédiat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05874221",
   "metadata": {},
   "outputs": [],
   "source": [
    "def perm_naif(A):\n",
    "    n = taille(A)\n",
    "    s = 0\n",
    "    for sigma in permutations(list(range(n))):\n",
    "        p = 1\n",
    "        for i in range(n):\n",
    "            p = p * A[i][sigma[i]]\n",
    "        s = s + p\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ec7e3a7",
   "metadata": {},
   "source": [
    "Le permanent d'une matrice $A$ de taille 2 est\n",
    "\n",
    "$$\\text{perm}(A)=A_{00}A_{11}+A_{10}A_{01}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44b2b011",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(2)\n",
    "print(perm_naif(A))\n",
    "print_mat(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f7d2836",
   "metadata": {},
   "source": [
    "Le permanent d'une matrice $A$ de taille 3 est\n",
    "\n",
    "$$\\text{perm}(A)=A_{00}A_{11}A_{22}+A_{01}A_{12}A_{20}+A_{02}A_{10}A_{21}+A_{00}A_{12}A_{21}+A_{01}A_{10}A_{22}+A_{02}A_{11}A_{20}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a38c13ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(3, 1, 3)\n",
    "print(perm_naif(A))\n",
    "print_mat(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70398ce4",
   "metadata": {},
   "source": [
    "Tentons une matrice de taille 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "69aede24",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(6)\n",
    "print_mat(A)\n",
    "print(perm_naif(A))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cfee089",
   "metadata": {},
   "source": [
    "Évidemment, nous pouvons avoir un doute sur la correction de la réponse. N'avons-nous pas commis une erreur dans notre code ? Un lecteur motivé pourrait calculer à la main les 720 termes de la somme qui définit le permanent de $A$, chacun de ces termes étant un produit de 6 facteurs ...\n",
    "\n",
    "Lorsque nous aurons d'autres algorithmes de calcul du permanent, nous pourrons comparer les valeurs renvoyées."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16b3279a",
   "metadata": {},
   "source": [
    "### 1.5 La complexité de `perm_naif`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d947272f",
   "metadata": {},
   "source": [
    "Pour tout $n\\in\\mathbb N$, appelons $C_n$ le nombre d'opérations *arithmétiques* sur des coefficients de la matrice (addition, multiplication) effectuées par `perm_naif` lors du calcul du permanent d'une matrice $n\\times n$.\n",
    "\n",
    "Pour chaque permutation $\\sigma\\in\\mathfrak S_n$, la fonction effectue $n$ multiplications et 1 addition. Comme il y a $n!$ permutations, on a donc\n",
    "\n",
    "$$C_n=(n+1)\\times n!=(n+1)!$$\n",
    "\n",
    "Notons que la valeur de $C_n$ ne prend pas en compte les opérations nécessaires pour engendrer les permutations de $\\mathfrak S_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "14301bec",
   "metadata": {},
   "outputs": [],
   "source": [
    "def complexite_naif(n): return math.factorial(n + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "803a4b6d",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(11):\n",
    "    print('%3d%10d' % (n, complexite_naif(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cec6a427",
   "metadata": {},
   "source": [
    "Quel est le temps réel mis par `perm_naif` pour calculer un permanent ? La fonction `temps` prend en paramètres une fonction $f$ et un entier $n$. Elle renvoie le temps mis par le calcul de $f(A)$, où $A$ est une matrice de taille $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58e6cfaa",
   "metadata": {},
   "outputs": [],
   "source": [
    "def temps(f, n):\n",
    "    A = randmat(n, 0, 1)\n",
    "    t1 = time.time()\n",
    "    p = f(A)\n",
    "    t2 = time.time()\n",
    "    return t2 - t1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "537f39b4",
   "metadata": {},
   "source": [
    "Notons $T_n$ le temps mis par `perm_naif` pour calculer le permanent d'une matrice de taille $n$. On a $T_n\\simeq KC_n$ où $K$ est une constante qui dépend de la machine. Quelle est la valeur de $K$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c94cb133",
   "metadata": {},
   "outputs": [],
   "source": [
    "t9 = temps(perm_naif, 9)\n",
    "K_naif = t9 / complexite_naif(9)\n",
    "print(K_naif)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6fa556cb",
   "metadata": {},
   "source": [
    "La fonction ci-dessous renvoie une estimation du temps mis par `perm_naif` pour un calcul de permanent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "85ae92ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "def temps_estime_naif(n):\n",
    "    return K_naif * complexite_naif(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "26a06941",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(21):\n",
    "    print('%3d%10.2es' % (n, temps_estime_naif(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a09dfbf",
   "metadata": {},
   "source": [
    "Ainsi, le temps estimé pour le calcul d'un permanent de taille 20 est $1.5\\times10^{13}$ secondes, c'est à dire environ ... $500000$ ans."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89f1d6a1",
   "metadata": {},
   "source": [
    "## 2. Quelques propriétés du permanent"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97be635f",
   "metadata": {},
   "source": [
    "Cette section ne contient pas de code. On y montre que le permanent possède des propriétés très analogues à celles du déterminant."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc7a6abe",
   "metadata": {},
   "source": [
    "### 2.1 Permanent et transposition"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91ad408a",
   "metadata": {},
   "source": [
    "**Proposition.** Soit $A\\in\\mathcal M_n(\\mathbb K)$. On a $\\text{perm}(A)=\\text{perm}(A^T)$.\n",
    "\n",
    "**Démonstration.** Dans les produits de la formule du permanent, posons $j=\\sigma(i)$. Il vient\n",
    "\n",
    "$$\\text{perm}(A)=\\sum_{\\sigma\\in\\mathfrak S_n}\\prod_{0\\le j<n}A_{\\sigma^{-1}(j)j}$$\n",
    "\n",
    "Posons ensuite dans la somme $\\tau=\\sigma^{-1}$. Lorsque $\\sigma$ décrit $\\mathfrak S_n$, $\\tau$ fait de même, et donc\n",
    "\n",
    "$$\\text{perm}(A)=\\sum_{\\tau\\in\\mathfrak S_n}\\prod_{0\\le j<n}A_{\\tau(j)j}=\\sum_{\\tau\\in\\mathfrak S_n}\\prod_{0\\le j<n}(A^T)_{j\\tau(j)}=\\text{perm}(A^T)$$\n",
    "\n",
    "**Remarque.** Toutes les propriétés du permanent relatives aux lignes des matrices sont donc également vraies pour les colonnes, et vice versa."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5887e63",
   "metadata": {},
   "source": [
    "### 2.2 Permanent d'une matrice triangulaire."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bef6537b",
   "metadata": {},
   "source": [
    "**Proposition.** Soit $A\\in\\mathcal M_n(\\mathbb K)$ une matrice triangulaire. On a \n",
    "\n",
    "$$\\text{perm}(A)=\\prod_{i=0}^{n-1}A_{ii}$$\n",
    "\n",
    "**Démonstration.** Supposons par exemple $A$ triangulaire supérieure, de sorte que pour tous $i,j\\in\\bar n$, $i>j\\implies A_{ij}=0$. Soit $\\sigma\\in\\mathfrak S_n$. Supposons $\\prod_{i=0}^{n-1}A_{i\\sigma(i)}\\ne 0$. On a alors pour tout $i\\in\\bar n$, $\\sigma(i)\\le i$, ce qui entraîne (récurrence sur $i$) que $\\sigma=id$. Ainsi, tous les termes de la somme qui définit le permanent sont nuls, sauf peut-être celui pour $\\sigma=id$, qui vaut $\\prod_{i=0}^{n-1}A_{ii}$.\n",
    "\n",
    "Si $A$ est triangulaire inférieure, il suffit de considérer $A^T$  pour se ramener à ce qui précède."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea8fac18",
   "metadata": {},
   "source": [
    "### 2.3 Multilinéarité"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa79c9db",
   "metadata": {},
   "source": [
    "Nous pouvons voir le permanent d'une matrice comme une fonction de ses $n$ lignes. On dispose donc de la fonction de $n$ variables \n",
    "\n",
    "$$\\text{perm}:\\mathcal M_{1n}(\\mathbb K)\\times\\ldots\\times\\mathcal M_{1n}(\\mathbb K)\\longrightarrow \\mathbb K$$\n",
    "\n",
    "**Proposition.** La fonction $\\text{perm}$ est $n$-linéaire symétrique.\n",
    "\n",
    "**Démonstration.** Soient $L'_0,L''_0,L_1,\\ldots,L_{n-1}\\in\\mathcal M_{1n}(\\mathbb K)$. Notons $A'$ la matrice dont les lignes sont $L'_0,L_1,\\ldots,L_{n-1}$ et $A''$ la matrice dont les lignes sont $L''_0,L_1,\\ldots,L_{n-1}$. On a, pour tout $\\sigma\\in\\mathfrak S_n$,\n",
    "\n",
    "$$(L'_0+L''_0)_{\\sigma(0)}\\prod_{1\\le i< n} (L_i)_{\\sigma(i)}=(L'_0)_{\\sigma(0)}\\prod_{1\\le i< n} (L_i)_{\\sigma(i)}+(L''_0)_{\\sigma(0)}\\prod_{1\\le i< n} (L_i)_{\\sigma(i)}=\\prod_{0\\le i< n} A'_{i\\sigma(i)}+\\prod_{0\\le i< n} A''_{i\\sigma(i)}$$\n",
    "\n",
    "De là,\n",
    "\n",
    "$$\\begin{array}{lll}\n",
    "\\text{perm}(L'_0+L''_0,L_1,\\ldots,L_{n-1})&=&\\sum_{\\sigma\\in\\mathfrak S_n}(\\prod_{0\\le i< n} A'_{i\\sigma(i)}+\\prod_{0\\le i< n} A''_{i\\sigma(i)})\\\\\n",
    "&=&\\sum_{\\sigma\\in\\mathfrak S_n}\\prod_{0\\le i< n} A'_{i\\sigma(i)}+\\sum_{\\sigma\\in\\mathfrak S_n}\\prod_{0\\le i< n} A''_{i\\sigma(i)}\\\\\n",
    "&=&\\text{perm}(A')+\\text{perm}(A'')\\\\\n",
    "&=&\\text{perm}(L'_0,L_1,\\ldots,L_{n-1})+\\text{perm}(L''_0,L_1,\\ldots,L_{n-1})\n",
    "\\end{array}$$\n",
    "\n",
    "On laisse au lecteur le soin de vérifier que si $\\lambda\\in\\mathbb K$ et $L_0,\\ldots,L_{n-1}\\in\\mathcal M_{1n}(\\mathbb K)$, alors\n",
    "\n",
    "$$\\text{perm}(\\lambda L_0,L_1,\\ldots,L_{n-1})=\\lambda\\ \\text{perm}(L_0,L_1,\\ldots,L_{n-1})$$\n",
    "\n",
    "Nous avons donc la linéarité de la fonction $\\text{perm}$ en sa première variable. Montrons la symétrie, nous aurons en prime la $n$-linéarité. Soient $L_0,\\ldots,L_{n-1}\\in\\mathcal M_{1n}(\\mathbb K)$. Soit $A\\in\\mathcal M_n(\\mathbb K)$ la matrice dont les lignes sont $L_0,\\ldots,L_{n-1}$. Soit $\\tau\\in\\mathfrak S_n$. Soit $A'$ la matrice dont les lignes sont $L_{\\tau(0)},\\ldots,L_{\\tau(n-1)}$. Montrons que $\\text{perm}(A')=\\text{perm}(A)$. On a\n",
    "\n",
    "$$\\text{perm}(A')=\\sum_{\\sigma\\in\\mathfrak S_n}\\prod_{0\\le i<n}A'_{i\\sigma(i)}=\\sum_{\\sigma\\in\\mathfrak S_n}\\prod_{0\\le i<n}A_{\\tau(i)\\sigma(i)}$$\n",
    "\n",
    "Dans chacun des produits, effectuons le changement d'indice $j=\\tau(i)$. Il vient\n",
    "\n",
    "$$\\text{perm}(A')=\\sum_{\\sigma\\in\\mathfrak S_n}\\prod_{0\\le i<n}A_{j(\\sigma\\tau^{-1})(j)}$$\n",
    "\n",
    "Posons maintenant dans la somme $\\gamma=\\sigma\\tau^{-1}$. Lorsque $\\sigma$ décrit $\\mathfrak S_n$, $\\gamma$ fait de même, et donc\n",
    "\n",
    "$$\\text{perm}(A')=\\sum_{\\gamma\\in\\mathfrak S_n}\\prod_{0\\le i<n}A_{j\\gamma(j)}=\\text{perm}(A)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b922fe1",
   "metadata": {},
   "source": [
    "Retenons en particulier les deux règles suivantes :\n",
    "\n",
    "- Échanger deux lignes ou deux colonnes d'une matrice ne change pas son permanent.\n",
    "- Multiplier une ligne ou une colonne d'une matrice par $\\lambda\\in\\mathbb K$ multiplie son permanent par $\\lambda$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b2f54fe",
   "metadata": {},
   "source": [
    "### 2.4 Non-propriétés du permanent"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54fda4dc",
   "metadata": {},
   "source": [
    "Il existe une règle qui est valable pour les déterminants et qui est d'une utilité cruciale pour leur calcul pratique : ajouter à une ligne d'une matrice une combinaison linéaire des autres lignes ne change pas son déterminant. Cette propriété des déterminants est liée à **l'alternance** (conséquence de **l'antisymétrie**) de la fonction déterminant alors que le permanent, quant à lui, est une fonction **symétrique**. \n",
    "\n",
    "\n",
    "Cette opération n'est donc pas possible pour les permanents. On ne peut pas effectuer d'opérations sur les lignes et les colonnes d'un permanent pour se ramener au permanent d'une matrice triangulaire qui, lui, est facile à calculer. Par exemple, soit $A=\\begin{pmatrix}1&3\\\\2&4\\end{pmatrix}$. Ajoutons la deuxième ligne de $A$ à la première pour obtenir $B=\\begin{pmatrix}3&7\\\\2&4\\end{pmatrix}$. On a $\\text{perm}(A)=10$ alors que $\\text{perm}(B)=26$.\n",
    "\n",
    "Notons également que le déterminant est un morphisme pour la multiplication matricielle, mais que le permanent ne l'est pas. Prenons par exemple $A=\\begin{pmatrix}1&3\\\\2&4\\end{pmatrix}$ et $B=\\begin{pmatrix}5&7\\\\6&8\\end{pmatrix}$. On a $AB=\\begin{pmatrix}23&31\\\\34&46\\end{pmatrix}$. De là,\n",
    "\n",
    "$$\\text{perm}(AB)=2112$$\n",
    "\n",
    "alors que\n",
    "\n",
    "$$\\text{perm}(A)\\times\\text{perm}(B)=10\\times 82=820$$\n",
    "\n",
    "Autre propriété qui n'est pas partagée par les permanents et les déterminants, deux matrices semblables n'ont pas nécessairement le même permanent. Le permanent n'est donc pas invariant par changement de base,  et il n'est donc pas possible de définir le permanent d'un endomorphisme d'un espace vectoriel, comme on le fait pour le déterminant."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd883283",
   "metadata": {},
   "source": [
    "### 2.5 La formule de Laplace"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e7cecf5",
   "metadata": {},
   "source": [
    "Nous allons voir que la formule de Laplace, qui permet de *développer* un déterminant par rapport à une ligne ou une colonne, est également vraie pour les permanents. Ceci nous donnera un algorithme de calcul du permanent différent de l'algorithme naïf."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a459be3d",
   "metadata": {},
   "source": [
    "Soit $A\\in\\mathcal M_n(\\mathbb K)$. Pour tous $i,j\\in[\\!|0,n-1|\\!]$, notons $A[i,j]$ la matrice obtenue en supprimant la ligne $i$ et la colonne $j$ de $A$. On a donc $A[i,j]\\in\\mathcal M_{n-1}(\\mathbb K)$.\n",
    "\n",
    "**Proposition.** Soit $A\\in\\mathcal M_n(\\mathbb K)$. \n",
    "\n",
    "- Développement par rapport à la ligne $i$ : pour tout $i\\in[\\!|0,n-1|\\!]$,\n",
    "\n",
    "$$\\text{perm}(A)=\\sum_{0\\le j< n}A_{ij}\\text{perm}(A[i,j])$$\n",
    "\n",
    "- Développement par rapport à la colonne $j$ : pour tout $j\\in[\\!|0,n-1|\\!]$,\n",
    "\n",
    "$$\\text{perm}(A)=\\sum_{0\\le i< n}A_{ij}\\text{perm}(A[i,j])$$\n",
    "\n",
    "Admettons provisoirement ce résultat et attaquons nous à l'écriture du code Python."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46a3e925",
   "metadata": {},
   "source": [
    "## 3. Implémentation de la formule de Laplace"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "949cab61",
   "metadata": {},
   "source": [
    "### 3.1 La fonction Python"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2b545a5",
   "metadata": {},
   "source": [
    "Voici la fonction calculant le permanent d'une matrice à l'aide de la formule de Laplace. Elle prend en paramètres une matrice $A$, un ensemble `lignes` de lignes et un ensemble `cols` de colonnes (c'est à dire deux objets Python de type `set`). La fonction renvoie le permanent de la matrice extraite de $A$ en prenant les lignes de $A$ de l'ensemble `lignes` et les colonnes de $A$ de l'ensemble `cols`. Elle utilise un développement suivant la ligne numéro $i$, où $i$ est la valeur renvoyée par `lignes.pop()`, c'est à dire un numéro de ligne « au hasard »."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5005811c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def perm_laplace0(A, lignes, cols):\n",
    "    if not lignes: return 1\n",
    "    else:\n",
    "        i = lignes.pop()\n",
    "        cols1 = cols.copy()\n",
    "        p = 0\n",
    "        for j in cols1:\n",
    "            cols.remove(j)\n",
    "            pij = perm_laplace0(A, lignes, cols)\n",
    "            cols.add(j)\n",
    "            p = p + A[i][j] * pij\n",
    "        lignes.add(i)\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6fd7f8c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def perm_laplace(A):\n",
    "    n = taille(A)\n",
    "    return perm_laplace0(A, set(range(n)), set(range(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef7b4109",
   "metadata": {},
   "source": [
    "Comparons les résultats renvoyés par `perm_naif` et `perm_laplace`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "29f8ee31",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(7)\n",
    "print(perm_naif(A))\n",
    "print(perm_laplace(A))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2aaff40a",
   "metadata": {},
   "source": [
    "Tout a l'air d'aller. Remarquons que notre fonction `perm_laplace` permet de calculer presque instantanément des permanents de matrices de tailles inférieures à 8 ou 9. Après, les choses se gâtent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0e5bc96a",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(10):\n",
    "    print('%3d%10.2es' % (n, temps(perm_laplace, n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52fd5f33",
   "metadata": {},
   "source": [
    "Pour une matrice de taille 9, il faut attendre environ 0.9 seconde (sur ma machine) pour avoir le résultat. Comme nous allons le voir dans l'étude théorique de complexité qui suit, on peut parier sur 9 secondes pour une matrice de taille 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0f5c98d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "t10 = temps(perm_laplace, 10)\n",
    "print(t10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72c1d4bb",
   "metadata": {},
   "source": [
    "Le calcul d'un permanent de taille 20 n'est toujours pas à notre portée, loin s'en faut."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7118b2ca",
   "metadata": {},
   "source": [
    "### 3.2 La complexité de la fonction `perm_laplace`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d171f7e8",
   "metadata": {},
   "source": [
    "Notons $C'_n$ le nombre d'opérations arithmétiques effectuées par la fonction `perm_laplace` lors du calcul du permanent d'une matrice de taille $n$.\n",
    "\n",
    "Tout d'abord, $C'_0=0$. Puis, pour tout $n\\ge 1$, le calcul du permanent d'une matrice de taille $n$ nécessite :\n",
    "\n",
    "- Le calcul de $n$ permanents de matrices de taille $n-1$.\n",
    "- $n$ multiplications\n",
    "- $n$ additions.\n",
    "\n",
    "Ainsi, $C'_n=nC'_{n-1}+2n$.\n",
    "\n",
    "**Proposition.** Pour tout $n\\in\\mathbb N$, \n",
    "\n",
    "$$C'_n=2n!\\sum_{k=0}^{n-1}\\frac 1 {k!}$$\n",
    "\n",
    "**Démonstration.** Faisons une récurrence sur $n$. Pour $n=0$, c'est clair puisque $C'_0=0$ et que la somme est nulle. Soit $n\\in\\mathbb N^*$. Supposons la propriété vérifiée pour $n-1$. On a alors\n",
    "\n",
    "$$C'_n=nC'_{n-1}+2n=n\\left(2(n-1)!\\sum_{k=0}^{n-2}\\frac 1 {k!}\\right)+2n=2n!\\sum_{k=0}^{n-2}\\frac 1 {k!}+2n$$\n",
    "\n",
    "Il reste à remarquer que\n",
    "\n",
    "$$2n=2n!\\frac 1{(n-1)!}$$\n",
    "\n",
    "Lorsque $n$ tend vers l'infini, la somme tend vers $e$. Ainsi, $C'_n\\sim 2e n!$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e670c78",
   "metadata": {},
   "outputs": [],
   "source": [
    "def complexite_laplace(n):\n",
    "    if n == 0: return 0\n",
    "    else:\n",
    "        return n * complexite_laplace(n - 1) + 2 * n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "557c9cfc",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(11):\n",
    "    print('%3d%10d%10d' % (n, complexite_naif(n), complexite_laplace(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6246cb60",
   "metadata": {},
   "source": [
    "On peut ainsi espérer que `perm_laplace` donnera de meilleurs résultats que `perm_naif`.\n",
    "\n",
    "Remarquons toutefois que nous n'avons compté dans le calcul de $C'_n$ que les opérations *arithmétiques*  effectuées par la fonction `perm_laplace`. En particulier, la ligne `cols1 = cols.copy()` a un coût en $O(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ebb57b3",
   "metadata": {},
   "source": [
    "### 3.3 Temps estimés"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6accb38a",
   "metadata": {},
   "source": [
    "Notons $T'_n$ le temps mis par `perm_lagrange` pour calculer le permanent d'une matrice de taille $n$. On a $T'_n\\simeq KC'_n$, où $K$ est une constante qui dépend de la machine utilisée. Quelle est la valeur de $K$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f319c112",
   "metadata": {},
   "outputs": [],
   "source": [
    "t10 = temps(perm_laplace, 10)\n",
    "K_laplace = t10 / complexite_laplace(10)\n",
    "print(K_laplace)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c7ce87a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def temps_estime_laplace(n):\n",
    "    return K_laplace * complexite_laplace(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ecef460f",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(21):\n",
    "    print('%3d%10.2es%10.2es' % (n, temps_estime_naif(n), temps_estime_laplace(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "214dd00c",
   "metadata": {},
   "source": [
    "Le calcul du permanent d'une matrice de taille 20 n'est toujours pas possible."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0da894fe",
   "metadata": {},
   "source": [
    "Comparons graphiquement les temps de calcul des fonctions `permanent_naif` et `permanent_laplace`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4de71e1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_temps(nmax, liste_fonctions_couleurs, log=True):\n",
    "    ns = range(nmax + 1)\n",
    "    funs = []\n",
    "    for f, c in liste_fonctions_couleurs:\n",
    "        ts = []\n",
    "        for n in ns:\n",
    "            A = randmat(n)\n",
    "            t1 = time.time()\n",
    "            p = f(A)\n",
    "            t2 = time.time()\n",
    "            ts.append(t2 - t1)\n",
    "        if log:\n",
    "            plt.semilogy(ns, ts, c, lw=1)\n",
    "            plt.semilogy(ns, ts, 'o'+ c, lw=1)\n",
    "        else:\n",
    "            plt.plot(ns, ts, c, lw=1)\n",
    "            plt.plot(ns, ts, 'o'+ c, lw=1)\n",
    "    plt.grid()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f874a676",
   "metadata": {},
   "source": [
    "En noir, le temps mis par `permanent_naif` pour calculer le permanent de matrices aléatoires de tailles entre 0 et 9. En rouge, le temps mis par `permanent_laplace` pour ces mêmes matrices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3743ed22",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_temps(9, [(perm_naif, 'k'), (perm_laplace, 'r')], log=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53eeffee",
   "metadata": {},
   "source": [
    "**Moralité** : Sans conviction, petit gain de temps pour la fonction `perm_laplace` ..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b502940",
   "metadata": {},
   "source": [
    "### 3.4 La preuve de la formule de Laplace"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8227db16",
   "metadata": {},
   "source": [
    "Montrons la formule de développement par rapport à une ligne. Par transposition, la formule de développement par rapport à une colonne s'en déduit. Soit $A\\in\\mathcal M_n(\\mathbb K)$. Notons $L_0,\\ldots,L_{n-1}$ les lignes de $A$. Soit $i\\in[\\!|0,n-1|\\!]$. Écrivons\n",
    "\n",
    "$$L_i=\\sum_{j=0}^{n-1}A_{ij}L'_j$$\n",
    "\n",
    "où $L'_j=(0\\ldots 0\\ 1\\ 0\\ldots 0)$ a un 1 en position $j$ et des zéros ailleurs. Par la $n$-linéarité du permanent,\n",
    "\n",
    "$$\\text{perm}(A)=\\sum_{j=0}^{n-1}A_{ij}\\text{perm}(L_0,\\ldots,L'_j,\\ldots,L_{n-1})$$\n",
    "\n",
    "où $L'_j$ se trouve en position $i$ ($L_i$ ne fait donc pas partie de l'énumération). Par la symétrie de la fonction permanent,\n",
    "\n",
    "$$\\text{perm}(L_0,\\ldots,L'_j,\\ldots,L_{n-1})=\\text{perm}(L_0,\\ldots,\\ldots,L_{n-1},L'_j)$$\n",
    "\n",
    "où $L_i$ n'apparaît pas dans l'énumération. Enfin, par des échanges de colonnes (qui conservent le permanent), on obtient\n",
    "\n",
    "$$\\text{perm}(L_0,\\ldots,\\ldots,L_{n-1},L'_j)=\\text{perm}(A')$$\n",
    "\n",
    "où $A'$ est la matrice définie par blocs par\n",
    "\n",
    "$$A'=\\begin{pmatrix}A[i,j]&0\\\\0&1\\end{pmatrix}$$\n",
    "\n",
    "Il reste à montrer que $\\text{perm}(A')=\\text{perm}(A[i,j])$. Pour cela, revenons à la définition du permanent. On a\n",
    "\n",
    "$$\\text{perm}(A')=\\sum_{\\sigma\\in\\mathfrak S_n}\\prod_{0\\le k<n}A'_{k\\sigma(k)}$$\n",
    "\n",
    "Remarquons que si $\\sigma(n-1)\\ne n-1$, alors $A'_{(n-1)\\sigma(n-1)}=0$. En notant\n",
    "\n",
    "$$\\mathfrak S'_n=\\{\\sigma\\in\\mathfrak S_n:\\sigma(n-1)=n-1\\}$$\n",
    "\n",
    "on a donc\n",
    "\n",
    "$$\\text{perm}(A')=\\sum_{\\sigma\\in\\mathfrak S'_n}\\prod_{0\\le k<n}A'_{k\\sigma(k)}=\\sum_{\\sigma\\in\\mathfrak S'_n}\\prod_{0\\le k<n-1}A'_{k\\sigma(k)}=\\sum_{\\sigma\\in\\mathfrak S'_n}\\prod_{0\\le k<n-1}A[i,j]_{k\\sigma(k)}$$\n",
    "\n",
    "L'ensemble $\\mathfrak S'_n$ est clairement en bijection avec $\\mathfrak S_{n-1}$ par la fonction qui à $\\sigma$ associe la restriction de $\\sigma$ à $[\\!|0,n-2|\\!]$. La somme ci-dessus est donc égale à $\\text{perm}(A[i,j])$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a692cd9",
   "metadata": {},
   "source": [
    "## 4. La formule de Ryser (I)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41df2868",
   "metadata": {},
   "source": [
    "### 4.1 La formule"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91c58676",
   "metadata": {},
   "source": [
    "La formule de Ryser permet de calculer le permanent d'une matrice plus efficacement qu'avec la formule de Laplace. Ne soyons pas trop exigeants, la complexité du calcul sera toujours exponentielle. Une implémentation très travaillée de cette formule, écrite dans un langage compilé, permet d'atteindre en une heure le calcul de permanents de matrices de taille environ 35. Voir par exemple le lien ci-dessous. Vous y apprendrez aussi que le calcul efficace de permanents est crucial pour certaines applications militaires.\n",
    "\n",
    "[https://apps.dtic.mil/sti/citations/AD1004183](https://apps.dtic.mil/sti/citations/AD1004183)\n",
    "\n",
    "**Proposition.** Soit $A\\in\\mathcal M_n(\\mathbb K)$. On a\n",
    "\n",
    "$$\\text{perm}(A)=\\sum_{S\\subseteq\\bar n}(-1)^{n-|S|}\\prod_{i=0}^{n-1}\\sum_{j\\in S}A_{ij}$$\n",
    "\n",
    "Nous prouverons cette formule un peu plus loin. Pour prendre un exemple, regardons $n=2$. L'ensemble $\\bar 2$ contient 4 parties qui sont $\\emptyset$, $\\{0\\}$, $\\{1\\}$ et $\\{0,1\\}$. La somme de la formule de Ryser est la somme de 4 termes ci-dessous :\n",
    "\n",
    "$$0-A_{00}A_{10}-A_{01}A_{11}+(A_{00}+A_{01})(A_{10}+A_{11})$$\n",
    "\n",
    "En développant, on obtient $A_{00}A_{11}+A_{01}A_{10}$ qui est bien le permanent de $A$.\n",
    "\n",
    "**Exercice.** Que donne la formule de Ryser pour une matrice de taille 1 ? De taille 0 ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56996c93",
   "metadata": {},
   "source": [
    "### 4.2 Énumérer les parties de $\\bar n$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9013a30",
   "metadata": {},
   "source": [
    "Une partie $S$ de $\\bar n$ peut être caractérisée par un $n$-uplet $(b_0,\\ldots,b_{n-1})\\in\\{0,1\\}^n$. Pour tout $i\\in\\bar n$, $i\\in S$ si et seulement si $b_i=1$. Énumérer les parties de $\\bar n$ revient donc à énumérer les listes de $n$ bits. Il existe pour cela une façon efficace de procéder : la technique des *codes de Gray*. Un code de Gray est une énumération des éléments de $\\{0,1\\}^n$ telle que le passage de chaque élément au suivant ne modifie qu'un seul bit. Nous ne montrerons pas le résultat suivant :\n",
    "\n",
    "**Pour passer du $i$ème code au $(i+1)$ème, on modifie le bit numéro $\\nu_2(i+1)$, où $\\nu_2$ est la** *valuation dyadique*."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "260f15c0",
   "metadata": {},
   "source": [
    "La fonction `nu2` renvoie la valuation dyadique de l'entier $n$, c'est à dire le plus grand entier naturel $k$ tel que $2^k$ divise $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7dbd98d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nu2(n):\n",
    "    k = 0\n",
    "    while n % 2 == 0:\n",
    "        k += 1\n",
    "        n = n // 2\n",
    "    return k"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15ed8561",
   "metadata": {},
   "source": [
    "Voici les valeurs de $\\nu_2(n)$ pour $n\\le 20$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4ce19254",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(1, 21): print('%3d' % n, end='')\n",
    "print()\n",
    "for n in range(1, 21): print('%3d' % nu2(n), end='')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96fe8a96",
   "metadata": {},
   "source": [
    "Et voici le graphe de $\\nu_2$ sur l'intervalle $[\\!|1,63|\\!]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "db8dfaa8",
   "metadata": {},
   "outputs": [],
   "source": [
    "xs = range(1, 64)\n",
    "ys = [nu2(x) for x in xs]\n",
    "plt.plot(xs, ys, 'k', lw=1)\n",
    "plt.plot(xs, ys, 'or', ms=4)\n",
    "plt.grid()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88c8132e",
   "metadata": {},
   "source": [
    "La fonction `parties` est un générateur. Elle énumère les éléments de $\\{0,1\\}^n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bd2b259b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def parties(n):\n",
    "    code = n * [0]\n",
    "    maxi = 2 ** n\n",
    "    c = 0\n",
    "    for k in range(maxi):\n",
    "        yield code\n",
    "        if k != maxi - 1:\n",
    "            c = c + 1\n",
    "            j = nu2(c)\n",
    "            code[j] = 1 - code[j]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8b0058af",
   "metadata": {},
   "outputs": [],
   "source": [
    "for S in parties(3): print(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1bc545f1",
   "metadata": {},
   "source": [
    "### 4.3 Une implémentation de la formule de Ryser"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9dcc4951",
   "metadata": {},
   "source": [
    "La fonction `somme_ligne` prend en paramètres\n",
    "\n",
    "- Une matrice $A$ de taille $n$.\n",
    "- Un entier $0\\le i < n$.\n",
    "- Une partie $S$ de $\\bar n$ représentée par une liste de $n$ bits.\n",
    "\n",
    "Elle renvoie $\\sum_{j\\in S}A_{ij}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d530bf88",
   "metadata": {},
   "outputs": [],
   "source": [
    "def somme_ligne(A, i, S):\n",
    "    n = taille(A)\n",
    "    s = 0\n",
    "    for j in range(n):\n",
    "        if S[j] == 1: s += A[i][j]\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d4153b3",
   "metadata": {},
   "source": [
    "Enfin, la fonction `perm_ryser` renvoie le permanent de la matrice $A$, calculé par la formule de Ryser. Ce code pourrait être amélioré : comme nous utilisons un code de Gray pour énumérer les parties de $\\bar n$, les sommes portant sur les lignes de $A$ ne sont modifiée que sur 1 terme lorsqu'on passe d'une partie de $\\bar n$ à la suivante. Avec un peu de soin, nous pourrions calculer la valeur des sommes à partir des sommes précédentes en temps $O(1)$. Ceci diviserait la complexité par un facteur $n$. Nous le ferons à la section suivante."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9eb45ac",
   "metadata": {},
   "source": [
    "Remarquons que comme nous énumérons les parties de $\\bar n$ par un code de Gray, si $S$ et $S'$ sont deux parties successives de l'énumération, on a $|S'|=|S|\\pm 1$. Ainsi, $\\varepsilon=(-1)^{|S|}$ est changé en $-\\varepsilon$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27b3a6db",
   "metadata": {},
   "outputs": [],
   "source": [
    "def perm_ryser(A):\n",
    "    n = taille(A)\n",
    "    perm = 0\n",
    "    eps = (-1) ** n\n",
    "    for S in parties(n):\n",
    "        p = 1\n",
    "        for i in range(n):\n",
    "            p = p * somme_ligne(A, i, S)\n",
    "        perm = perm + eps * p\n",
    "        eps = -eps\n",
    "    return perm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15e6bebf",
   "metadata": {},
   "source": [
    "Histoire de vérifier, comparons les nombres renvoyés par `prem_lagrange` et `perm_ryser`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "62d8ab81",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(5)\n",
    "print(perm_ryser(A), perm_laplace(A))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd82e6f1",
   "metadata": {},
   "source": [
    "Tout va bien, deux méthodes totalement différentes donnent le même résultat. \n",
    "\n",
    "Avec `perm_lagplace`, il ne nous était pas possible de caluler le permanent d'une matrice de taille 10 en moins de 30 secondes. Essayons avec `perm_ryser`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fcb56640",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(10)\n",
    "print(perm_ryser(A))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f285fe9b",
   "metadata": {},
   "source": [
    "Cette fois-ci, la réponse est immédiate. Voici les tailles de matrices pour lesquelles le temps de calcul est inférieur à 3 secondes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa0c1ef5",
   "metadata": {},
   "outputs": [],
   "source": [
    "t, n = 0, 0\n",
    "while t < 3:\n",
    "    print('%4d %10.2es' % (n, t))\n",
    "    n = n + 1\n",
    "    t = temps(perm_ryser, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa18d198",
   "metadata": {},
   "source": [
    "### 4.4 Complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7770429",
   "metadata": {},
   "source": [
    "Notons $C''_n$ le nombre d'opérations arithmétiques effectuées par la fonction `perm_ryser` lors du calcul du permanent d'une matrice de taille $n$ (sans compter les opérations effectuées pour énumérer les parties de $\\bar n$).\n",
    "\n",
    "Pour chaque partie $S$ de $\\bar n$, la fonction `perm_ryser` effectue\n",
    "\n",
    "- $n+1$ multiplications\n",
    "- $n|S|+1$ additions.\n",
    "\n",
    "Ainsi,\n",
    "\n",
    "$$C''_n=\\sum_{S\\in\\mathcal P(\\bar n)}(n|S|+n+2)=(n+2)2^n+n\\sum_{S\\in\\mathcal P(\\bar n)}|S|$$\n",
    "\n",
    "Calculons cette dernière somme. Pour tout $k\\le n$, notons \n",
    "\n",
    "$$\\mathcal P_k(\\bar n)=\\{S\\in\\mathcal P(\\bar n):|S|=k\\}$$\n",
    "\n",
    "On a \n",
    "\n",
    "$$\\sum_{S\\in\\mathcal P(\\bar n)}|S|=\\sum_{k=0}^n\\sum_{S\\in\\mathcal P_k(\\bar n)}|S|=\\sum_{k=0}^nk|\\mathcal P_k(\\bar n)|=\\sum_{k=0}^nk\\binom n k$$\n",
    "\n",
    "Remarquons que si $k\\ge 1$, alors\n",
    "\n",
    "$$k\\binom n k=n\\binom{n-1}{k-1}$$\n",
    "\n",
    "On a donc\n",
    "\n",
    "$$\\sum_{k=0}^nk\\binom n k=n\\sum_{k=1}^n\\binom {n-1} {k-1}=n2^{n-1}$$\n",
    "\n",
    "Ainsi,\n",
    "\n",
    "$$C''_n=(n+2)2^n+n^22^{n-1}=(n^2+2n+4)2^{n-1}\\sim n^22^{n-1}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aae24a8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def complexite_ryser(n):\n",
    "    return (n ** 2 + 2 * n + 4) * 2 ** (n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e74ccec",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(20):\n",
    "    print('%3d%10d' % (n, complexite_ryser(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1dc3d38d",
   "metadata": {},
   "source": [
    "Terminons par une comparaison graphique des temps de calculs des fonctions `perm_laplace` et `perm_ryser`. En abscisse, la taille des matrices. En ordonnées, les temps de calcul en coordonnées logarithmiques. En noir, la formule de Laplace, en rouge la formule de Ryser."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cafddabb",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_temps(10, [(perm_laplace, 'k'), (perm_ryser, 'r')], log=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08e5855d",
   "metadata": {},
   "source": [
    "**Moralité** : Cette fois-ci, le gain de temps est réel. Pour une matrice de taille $10$ la fonction `perm_ryser` est environ 1000 fois plus rapide que la fonction `perm_laplace`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f1264bad",
   "metadata": {},
   "source": [
    "### 4.5 Temps estimés"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f8fdc6e",
   "metadata": {},
   "source": [
    "Notons $T''_n$ le temps mis par `perm_ryser` pour calculer le permanent d'une matrice de taille $n$. On a $T''_n\\simeq KC''_n$ où $K$ est une constante. Quelle est la valeur de $K$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dbd016be",
   "metadata": {},
   "outputs": [],
   "source": [
    "t15 = temps(perm_ryser, 15)\n",
    "K_ryser = t15 / complexite_ryser(15)\n",
    "print(K_ryser)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58c082e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def temps_estime_ryser(n):\n",
    "    return K_ryser * complexite_ryser(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4286cfff",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(21):\n",
    "    print('%3d%10.2es%10.2es' % (n, temps_estime_laplace(n), temps_estime_ryser(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52eb6795",
   "metadata": {},
   "source": [
    "Le calcul d'un permanent de taille 20 par notre implémentation de la formule de Ryser demandera donc environ 1min 20s. C'est tout à fait faisable ! Le lecteur est invité à essayer, en décommentant la cellule ci-dessous. Nous ferons mieux bientôt ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44180194",
   "metadata": {},
   "outputs": [],
   "source": [
    "#A = randmat(20)\n",
    "#print(perm_ryser(A))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c3681d3",
   "metadata": {},
   "source": [
    "### 4.6 La preuve"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99bbd1a4",
   "metadata": {},
   "source": [
    "Il nous reste à prouver la formule de Ryser. Soit $A\\in\\mathcal M_n(\\mathbb K)$. Notons\n",
    "\n",
    "$$\\pi(A)=\\sum_{S}(-1)^{n-|S|}\\prod_{i=0}^{n-1}\\sum_{j\\in S}A_{ij}$$\n",
    "\n",
    "Où $S$ désigne une partie de $\\bar n$. On a, en développant le produit,\n",
    "\n",
    "$$\\pi(A)=\\sum_{S}\\sum_{(j_0,\\ldots,j_{n-1})\\in S^n}(-1)^{n-|S|}A_{0j_0}\\ldots A_{(n-1)j_{n-1}}$$\n",
    "\n",
    "Échangeons maintenant les deux sommes pour obtenir\n",
    "\n",
    "$$\\pi(A)=\\sum_{(j_0,\\ldots,j_{n-1})\\in {\\bar n}^n}\\alpha_{j_0\\ldots j_{n-1}}A_{0j_0}\\ldots A_{(n-1)j_{n-1}}$$\n",
    "\n",
    "où\n",
    "\n",
    "$$\\alpha_{j_0\\ldots j_{n-1}}=\\sum_{\\{j_0,\\ldots,j_{n-1}\\}\\subseteq S}(-1)^{n-|S|}$$\n",
    "\n",
    "Soient $j_0,\\ldots,j_{n-1}\\in\\bar n$. Soit $k$ le cardinal de l'ensemble $\\{j_0,\\ldots,j_{n-1}\\}$. Les ensembles $S$ contenant $j_0,\\ldots j_{n-1}$ sont de cardinaux $k$, $k+1$, ..., $n$. Pour tout $r\\in[|k,n-1|]$, il existe $\\binom{n-k}{r-k}$ tels ensembles. Ainsi,\n",
    "\n",
    "$$\\alpha_{j_0\\ldots j_{n-1}}=\\sum_{r=k}^{n}(-1)^{n-r}\\binom{n-k}{r-k}$$\n",
    "\n",
    "Posons $r'=r-k$ pour obtenir\n",
    "\n",
    "$$\\alpha_{j_0\\ldots j_{n-1}}=\\sum_{r=0}^{n-k}(-1)^{n-r-k}\\binom{n-k}{r}=(-1)^{n-k}\\sum_{r=0}^{n-k}(-1)^{r}\\binom{n-k}{r}=(-1)^{n-k}(1-1)^{n-k}=(-1)^{n-k}0^{n-k}$$\n",
    "\n",
    "- Si $k=n$, alors $\\alpha_{j_0\\ldots j_{n-1}}=1$.\n",
    "- Si $k<n$, alors $\\alpha_{j_0\\ldots j_{n-1}}=0$.\n",
    "\n",
    "Ainsi,\n",
    "\n",
    "$$\\pi(A)=\\sum_{(j_0,\\ldots,j_{n-1})\\in E_n}A_{0j_0}\\ldots A_{(n-1)j_{n-1}}$$\n",
    "\n",
    "où $E_n$ désigne l'ensemble des $n$-uplets $(j_0,\\ldots,j_{n-1})$ d'entiers distincts entre 0 et $n-1$. Il reste à remarquer que $\\mathfrak S_n$ est en bijection avec $E_n$ via l'application $\\phi:\\sigma\\longmapsto (\\sigma(0),\\ldots,\\sigma(n-1))$. En posant dans la somme ci-dessus $(j_0,\\ldots,j_{n-1})=\\phi(\\sigma)$, on obtient\n",
    "\n",
    "$$\\pi(A)=\\sum_{\\sigma\\in\\mathfrak S_n}A_{0\\sigma(0)}\\ldots A_{(n-1)\\sigma(n-1)}=\\text{perm}(A)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35da7139",
   "metadata": {},
   "source": [
    "## 5 Une meilleure implémentation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33c89dc7",
   "metadata": {},
   "source": [
    "### 5.1 Ryser, le retour"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6618aeb7",
   "metadata": {},
   "source": [
    "Comme nous l'avons déjà dit, il est possible d'améliorer la complexité temporelle de la fonction `perm_ryser`. L'idée est de garder en mémoire les valeurs des sommes qui interviennent dans la formule de Ryser. En énumérant les parties de $\\bar n$ par un code de Gray, on ne change qu'un terme de chacune des sommes. Il est donc possible de recalculer *toutes* les sommes en temps $O(n)$, et non plus *chaque* somme en temps $O(n)$. Voici le code, il est un peu plus compliqué que le code de `perm_ryser`, mais nous allons voir que l'on gagne en efficacité."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "104d3afa",
   "metadata": {},
   "outputs": [],
   "source": [
    "def perm_ryser2(A):\n",
    "    n = taille(A)\n",
    "    perm = 0\n",
    "    eps = (-1) ** n\n",
    "    S = n * [0]\n",
    "    sommes = n * [0]\n",
    "    p2n = 2 ** n\n",
    "    for k in range(p2n):\n",
    "        p = 1\n",
    "        for i in range(n):\n",
    "            p = p * sommes[i]\n",
    "        perm = perm + eps * p\n",
    "        eps = -eps\n",
    "        if k < p2n - 1:\n",
    "            j = nu2(k + 1)\n",
    "            for i in range(n):\n",
    "                if S[j] == 1: sommes[i] = sommes[i] - A[i][j]\n",
    "                else: sommes[i] = sommes[i] + A[i][j]\n",
    "            S[j] = 1 - S[j]\n",
    "    return perm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80d765ce",
   "metadata": {},
   "source": [
    "Tout d'abord, constatons que les fonctions `perm_ryser` et `perm_ryser2` renvoient les mêmes résultats."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f184d859",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(10)\n",
    "print(perm_ryser(A), perm_ryser2(A))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05b0081a",
   "metadata": {},
   "source": [
    "Comparons les temps mis par nos deux fonctions pour calculer le permanent d'une matrice de taille 17 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67c3ddc1",
   "metadata": {},
   "outputs": [],
   "source": [
    "t1 = temps(perm_ryser, 17)\n",
    "print('Temps ryser  : %10.2es' % t1)\n",
    "t2 = temps(perm_ryser2, 17)\n",
    "print('Temps ryser2 : %10.2es' % t2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bacba1ed",
   "metadata": {},
   "source": [
    "La fonction `perm_ryser2` nous permet de calculer sans trop de difficulté (une dizaine de secondes sur ma machine) le permanent d'une matrice de taille 20. Rappelons-nous que la fonction `perm_ryser` mettait 1min20s pour effectuer ce même calcul."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb7f569a",
   "metadata": {},
   "outputs": [],
   "source": [
    "print('%10.2es' % temps(perm_ryser2, 20))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2f10b7f",
   "metadata": {},
   "source": [
    "Et voici pour terminer le graphique des temps comparés entre les fonctions `perm_ryser` et `perm_ryser2`. Le gain est nettement appréciable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a9502cdd",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_temps(16, [(perm_ryser, 'k'), (perm_ryser2, 'r')], log=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4683233e",
   "metadata": {},
   "source": [
    "### 5.2 La complexité de `perm_ryser2`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43cec71b",
   "metadata": {},
   "source": [
    "La fonction `perm_ryser2` effectue une boucle de $2^n$ itérations sur la variable $k$. Pour chaque itération, on effectue\n",
    "\n",
    "- $n$ multiplications dans la boucle sur $i$.\n",
    "- 1 addition et 1 multiplication juste après.\n",
    "- Si $k\\ne 2^n-1$, $|S| + 1$ additions.\n",
    "\n",
    "Pour ne pas trop alourdir notre analyse, supposons que les $|S|+1$ additions sont aussi effectuées lorsque $k=2^n-1$. Notons $C'''_n$ le nombre total d'opérations arithmétiques. On a\n",
    "\n",
    "$$C'''_n=2^n(n+2)+\\sum_{S\\subseteq\\bar n}(|S|+1)=2^n(n+3)+\\sum_{S\\subseteq\\bar n}|S|$$\n",
    "\n",
    "Que vaut la dernière somme ? Réordonnons suivant le cardinal de $S$. On a\n",
    "\n",
    "$$\\sum_{S\\subseteq\\bar n}|S|=\\sum_{k=0}^n\\sum_{|S|=k}|S|=\\sum_{k=0}^nk\\binom n k$$\n",
    "\n",
    "Cette somme a déjà été calculée lors de l'étude de la complexité de `perm_ryser`. Elle vaut $n2^{n-1}$. Ainsi,\n",
    "\n",
    "$$C'''_n=(n+3)2^n+n2^{n-1}=3(n+2)2^{n-1}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36c1ea64",
   "metadata": {},
   "outputs": [],
   "source": [
    "def complexite_ryser2(n):\n",
    "    return 3 * (n + 2) * 2 ** (n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "92ec5408",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(20):\n",
    "    print('%10d%10d' % (complexite_ryser(n), complexite_ryser2(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfa126a7",
   "metadata": {},
   "source": [
    "Notons $T'''_n$ le temps mis par `perm_ryser2` pour calculer le permanent d'une matrice de taille $n$. On a $T'''_n\\simeq KC'''_n$, où $K$ est une constante. Quelle est la valeur de $K$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bf5e9e0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "t17 = temps(perm_ryser2, 17)\n",
    "K_ryser2 = t17 / complexite_ryser2(17)\n",
    "print(K_ryser2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6c832b20",
   "metadata": {},
   "outputs": [],
   "source": [
    "def temps_estime_ryser2(n):\n",
    "    return K_ryser2 * complexite_ryser2(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e79888d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(21):\n",
    "    print('%3d%10.2es%10.2es' % (n, temps_estime_ryser(n), temps_estime_ryser2(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f9447c5",
   "metadata": {},
   "source": [
    "Pour une matrice de taille 20, le temps estimé correspond bien au temps réel.\n",
    "\n",
    "Serions-nous maintenant en mesure de calculer le permanent d'une matrice de taille 30 ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "49299e2e",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(temps_estime_ryser2(30) / 3600)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5df99655",
   "metadata": {},
   "source": [
    "Le calcul d'un permanent de taille 30 par notre seconde implémentation de la formule de Ryser demandera donc environ 4 heures. C'est long, mais c'est faisable."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1fb6ae8",
   "metadata": {},
   "source": [
    "## 6. Retour aux mariages parfaits"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9c7bd52",
   "metadata": {},
   "source": [
    "Le lecteur se sent probablement un peu frustré de connaître le *nombre* de mariages parfaits d'un graphe bipartite est d'être incapable de *déterminer* un mariage parfait. Comme nous l'avons déjà dit au début de ce notebook, il existe des algorithmes en temps polynomial permettant de calculer un mariage parfait, si celui-ci existe. Un de ces algorithmes repose sur l'agorithme de *Ford-Fulkerson*, dont la description demanderait à elle seule tout un article.\n",
    "\n",
    "Nous allons dans ce qui va suivre nous contenter d'écrire une fonction naïve faisant le travail."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9800fa19",
   "metadata": {},
   "source": [
    "### 6.1 Trouver un mariage parfait"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3d2de7b",
   "metadata": {},
   "source": [
    "La fonction `est_mariage_parfait` prend en paramètre un graphe bipartite $G$ ayant $2n$ sommets. L'ensemble des sommets de $G$ est $S=X\\cup Y$ où $X=\\{x_0,\\ldots,x_{n-1}\\}$ et $Y=\\{y_0,\\ldots,y_{n-1}\\}$. Les arêtes de $G$ ont une de leurs extrémités dans $X$ et l'autre extrémité dans $Y$. Rappelons que le graphe $G$ est modélisé par une liste Python $G$ de longueur $n$. Pour $i\\in\\bar n$, $G[i]$ est une liste d'entiers entre 0 et $n-1$. L'entier $j$ est dans $G[i]$ si et seulement si il existe une arête d'extrémités $x_i$ et $y_j$.\n",
    "\n",
    "La fonction prend aussi en paramètre une permutation $\\sigma$, représentée par la liste $[\\sigma(0),\\ldots,\\sigma(n-1)]$. La fonction renvoie `True` si pour tout $i\\in\\bar n$, il existe une arête de $G$ d'extrémités $x_i$ et $y_{\\sigma(i)}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0b66cb59",
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_mariage_parfait(G, s):\n",
    "    n = len(s)\n",
    "    for i in range(n):\n",
    "        if s[i] not in G[i]: return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d3764cc",
   "metadata": {},
   "source": [
    "La fonction `trouver_mariage_parfait` recherche naïvement un mariage parfait pour le graphe bipartite $G$ de taille $2n$ en testant toutes les permutations $\\sigma\\in\\mathfrak S_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "59b0212b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trouver_mariage_parfait(G):\n",
    "    n = len(G)\n",
    "    for s in permutations(list(range(n))):\n",
    "        if est_mariage_parfait(G, s): return s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61b33e2b",
   "metadata": {},
   "source": [
    "Testons. Dans la cellule ci-dessous, si le graphe bipartite aléatoire $G$ ne possède pas de mariage parfait, la variable $s$ vaut `None`. Dans ce cas, réévaluer la cellule jusquà ce que $s$ soit une liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "34ee8e33",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = graphe_bipartite_alea(9)\n",
    "s = trouver_mariage_parfait(G)\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fda472a",
   "metadata": {},
   "source": [
    "Réécrivons une fonction de tracé de graphe en faisant aussi passer en paramère un mariage parfait du graphe. La fonction affiche les arêtes du mariage parfait en gras et les autres arêtes en pointillés fins."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "00206827",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_graph2(G, s):\n",
    "    n = len(G)\n",
    "    xs = list(range(n))\n",
    "    for i in range(n):\n",
    "        for j in G[i]: plt.plot([i, j], [0, 1], '--k', lw=0.5)\n",
    "    if s != None:\n",
    "        for i in range(n):\n",
    "            plt.plot([i, s[i]], [0, 1], 'k', lw=1)\n",
    "    plt.plot(xs, n * [1], 'or', ms=10)\n",
    "    plt.plot(xs, n * [0], 'ok', ms=10)\n",
    "    \n",
    "    plt.axis('off')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a898b924",
   "metadata": {},
   "source": [
    "Évaluer la cellule ci-dessous jusqu'à ce que le graphe aléatoire $G$ possède un mariage parfait, puis passer à la cellule suivante qui fait le tracé ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fb0904b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = graphe_bipartite_alea(8, 0.3)\n",
    "s = trouver_mariage_parfait(G)\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d434b45",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_graph2(G, s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f919ca04",
   "metadata": {},
   "source": [
    "### 6.2 Trouver tous les mariages parfaits"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27e59f9b",
   "metadata": {},
   "source": [
    "Pour trouver **tous** les mariages parfaits, rien de plus facile ni de plus inefficace. Il suffit de modifier un peu le code de `trouver_mariage_parfait`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dcb3e70d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tous_mariage_parfaits(G):\n",
    "    n = len(G)\n",
    "    mp = []\n",
    "    for s in permutations(list(range(n))):\n",
    "        if est_mariage_parfait(G, s): mp.append(s)\n",
    "    return mp"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "207881a0",
   "metadata": {},
   "source": [
    "Testons sur un graphe bipartite ayant 16 sommets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "25499273",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = graphe_bipartite_alea(8, 0.4)\n",
    "mp = tous_mariage_parfaits(G)\n",
    "print(perm_ryser2(matrice_biadjacence(G)), len(mp))\n",
    "for s in mp: print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e951e6b1",
   "metadata": {},
   "source": [
    "## 7. Pour terminer - Couverture d'un graphe par des cycles"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f2419f7",
   "metadata": {},
   "source": [
    "Cette dernière section a deux objectifs.\n",
    "\n",
    "- Montrer que la notion de permanent permet de compter autre chose que des mariages parfaits.\n",
    "- Calculer explicitement le permanent de quelques matrices particulières."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0f23ed9",
   "metadata": {},
   "source": [
    "### 7.1 Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc7714aa",
   "metadata": {},
   "source": [
    "Si $G=(S,A)$ est un graphe, un *sous-graphe* de $G$ est un graphe $G'=(S',A')$ tel que $S'\\subseteq S$ et $A'\\subseteq A$. Notons que comme $G'$ est un graphe, ceci implique $A'\\subseteq S'\\times S'$.\n",
    "\n",
    "Si $G=(S,A)$ est un graphe et $x,y\\in S$, notons $x\\rightarrow y$ lorsque $(x,y)\\in A$.\n",
    "\n",
    "**Définition.** Soit $k\\ge 1$. Un *cycle de longueur $k$* du graphe $G$ est un sous-graphe $\\Gamma=(S',A')$ de $G$ tel que $|S'|=k$ et il existe une numérotation $S'=\\{x_0,\\ldots,x_{k-1}\\}$ de l'ensemble des sommets de $\\Gamma$ telle que, dans le graphe $\\Gamma$,\n",
    "\n",
    "- $x_0\\rightarrow x_1\\rightarrow x_{k-1}\\rightarrow x_0$.\n",
    "- Les seules arêtes de $\\Gamma$ sont celles données ci-dessus ($\\Gamma$ possède donc $k$ arêtes).\n",
    "\n",
    "L'ensemble $S'$ est le *support* du cycle $\\Gamma$. Nous noterons $\\Gamma=[x_0,\\ldots,x_{n-1}]$. Remarquons la non-unicité de cette notation : un cycle n'a pas de « début ».\n",
    "\n",
    "**Exemples.** Un cycle de longueur 1 est un graphe $\\Gamma=[x]$, c'est à dire une boucle sur le sommet $x$. Un cycle de longueur 2 est un graphe $\\Gamma=[x,y]$ où $x,y$ sont deux sommets distincts.\n",
    "\n",
    "**Définition.** Une *couverture* du graphe $G$ (par des cycles de supports disjoints) est un ensemble de cycles de $G$ dont les supports forment une partition de l'ensemble des sommets de $G$.\n",
    "\n",
    "**Question.** Soit $G$ un graphe. Combien $G$ possède-t-il de couvertures ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "902fae5c",
   "metadata": {},
   "source": [
    "### 7.2 Matrice d'adjacence"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef6911ee",
   "metadata": {},
   "source": [
    "Soit $G$ un graphe orienté. Numérotons les sommets de $G$ en notant $S=\\{x_0,\\ldots,x_{n-1}\\}$ l'ensemble des sommets du graphe.\n",
    "\n",
    "**Définition.** La *matrice d'adjacence* de $G$ est la matrice $A^G\\in\\mathcal M_n(\\{0,1\\})$ définie, pour tous $i,j\\in\\bar n$ par $A_{ij}=1$ si $x_i\\rightarrow x_j$, et $A_{ij}=0$ sinon."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5b4d608",
   "metadata": {},
   "source": [
    "### 7.3 Quelques exemples"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f944f01",
   "metadata": {},
   "source": [
    "Donnons quelques exemples de graphes très classiques."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "334da817",
   "metadata": {},
   "source": [
    "#### 7.3.1 Le graphe complet $K_n$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a45685f",
   "metadata": {},
   "source": [
    "Le graphe complet à $n$ sommets, que l'on note classiquement $K_n$, a $\\bar n$ pour ensemble des sommets. Pour tous $i,j\\in\\bar n$ tels que $i\\ne j$, $i\\rightarrow j$. La fonction `complet` renvoie la matrice d'adjacence d'un tel graphe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9da68f6b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def complet(n):\n",
    "    A = matrice(n, 1)\n",
    "    for i in range(n): A[i][i] = 0\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a66e7a0",
   "metadata": {},
   "source": [
    "Voici la matrice d'adjacence de $K_5$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a36c295a",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = complet(5)\n",
    "print_mat(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c15ef52",
   "metadata": {},
   "source": [
    "Voici une illustration graphique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "af9b09f2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_Kn(n):\n",
    "    ts = [2 * k * math.pi / n for k in range(n + 1)]\n",
    "    xs = [math.cos(t) for t in ts]\n",
    "    ys = [math.sin(t) for t in ts]\n",
    "    for i in range(n + 1):\n",
    "        for j in range(n + 1):\n",
    "            if i != j:\n",
    "                plt.plot([xs[i], xs[j]], [ys[i], ys[j]], 'k', lw=0.5)\n",
    "    plt.plot(xs, ys, 'or')\n",
    "    plt.axis('off')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "42f50494",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (5, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "449e114b",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_Kn(9)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7934cac2",
   "metadata": {},
   "source": [
    "#### 7.3.2 Le cycle $C_n$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "797053ec",
   "metadata": {},
   "source": [
    "Soit $n\\ge 2$. Le cycle (non orienté) à $n$ sommets $C_n$ a $\\bar n$ pour ensemble des sommets. Ses arêtes sont \n",
    "\n",
    "- $0\\rightarrow 1\\rightarrow\\ldots\\rightarrow n-1\\rightarrow 0$\n",
    "- $0\\rightarrow n-1\\rightarrow\\ldots\\rightarrow 1\\rightarrow 0$\n",
    "\n",
    "Remarquons que $C_n$ n'est pas un cycle, au sens défini plus haut : il n'est pas *orienté*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "401a82cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cycle(n):\n",
    "    A = matrice(n, 0)\n",
    "    for i in range(n):\n",
    "        if i > 0: A[i][i - 1] = 1\n",
    "        if i < n - 1: A[i][i + 1] = 1\n",
    "    A[n - 1][0] = 1\n",
    "    A[0][n - 1] = 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac3fd437",
   "metadata": {},
   "source": [
    "Voici la matrice d'adjacence de $C_6$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6f4ff80",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = cycle(6)\n",
    "print_mat(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cba2cfa",
   "metadata": {},
   "source": [
    "Voici une illustration graphique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7ab540fc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_Cn(n):\n",
    "    ts = [2 * k * math.pi / n for k in range(n + 1)]\n",
    "    xs = [math.cos(t) for t in ts]\n",
    "    ys = [math.sin(t) for t in ts]\n",
    "    for i in range(n):\n",
    "        plt.plot([xs[i], xs[i + 1]], [ys[i], ys[i + 1]], 'k', lw=0.5)\n",
    "    plt.plot(xs, ys, 'or')\n",
    "    plt.axis('off')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6ef2de17",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_Cn(9)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57c3813c",
   "metadata": {},
   "source": [
    "#### 7.3.3 Le graphe bipartite complet $K_{n,n}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5126c0b",
   "metadata": {},
   "source": [
    "Soit $n\\ge 1$. Le graphe bipartite complet $K_{n,n}$ possède $2n$ sommets qui sont les entiers de $\\overline{2n}$. Pour tout $i\\in\\overline n$ et tout $j\\in[\\!|n,2n-1|\\!]$, $i\\rightarrow j$ et $j\\rightarrow i$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2303528a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bipartite_complet(n):\n",
    "    A = matrice(2 * n, 0)\n",
    "    for i in range(n):\n",
    "        for j in range(n, 2 * n):\n",
    "            A[i][j] = 1\n",
    "            A[j][i] = 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76eb3198",
   "metadata": {},
   "source": [
    "Voici la matrice d'adjacence de $K_{3,3}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90a44ce7",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = bipartite_complet(3)\n",
    "print_mat(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4fb40f6",
   "metadata": {},
   "source": [
    "Voici une illustration graphique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17ef8a24",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_Knn(n):\n",
    "    G = n * [None]\n",
    "    for i in range(n):\n",
    "        G[i] = list(range(n))\n",
    "    plot_graph(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "76b62cea",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (8, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d5bc2dd9",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_Knn(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b57a1a5a",
   "metadata": {},
   "source": [
    "#### 7.3.4 Le cube $Q_n$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b03237c4",
   "metadata": {},
   "source": [
    "Terminons par un exemple un peu plus compliqué, celui de l'hypercube $Q_n$. Il y a de nombreuses façons de présenter celui-ci, nous choisissons la plus simple pour ce que nous voulons faire. Pour tout $n\\ge 0$, l'ensemble des sommets de $Q_n$ est $S=\\overline{2^n}$. Pour tous $i, j\\in S$, $i\\rightarrow j$ (et $j\\rightarrow i$) si et seulement si les entiers $i$ et $j$ diffèrent d'un seul bit."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c3e4b7c",
   "metadata": {},
   "source": [
    "La fonction `bits` prend en paramètres deux entiers $x$ et $n$ tels que $x<2^n$. Elle renvoie une liste $[b_0,\\ldots,b_{n-1}]$ telle que les $b_k$ valent 0 ou 1 et\n",
    "\n",
    "$$\\sum_{k=0}^{n-1}b_k2^k=x$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9ee72646",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bits(x, n):\n",
    "    s = []\n",
    "    for k in range(n):\n",
    "        s.append(x % 2)\n",
    "        x = x // 2\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4935c5c1",
   "metadata": {},
   "source": [
    "La fonction `nombre_bits_distincts` prend en paramètres deux listes $x$ et $y$ de même longueur. Elle renvoie le nombre de termes distincts des deux listes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63a5d4fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_bits_distincts(x, y):\n",
    "    n = len(x)\n",
    "    c = 0\n",
    "    for k in range(n):\n",
    "        if x[k] != y[k]: c += 1\n",
    "    return c"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b5c2cc7",
   "metadata": {},
   "source": [
    "Enfin, la fonction `cube` renvoie la matrice d'adjacence de $Q_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "769194ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cube(n):\n",
    "    p2n = 2 ** n\n",
    "    A = matrice(p2n, 0)\n",
    "    for i in range(p2n):\n",
    "        bi = bits(i, n)\n",
    "        for j in range(p2n):\n",
    "            bj = bits(j, n)\n",
    "            if nombre_bits_distincts(bi, bj) == 1:\n",
    "                A[i][j] = 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d1b8921",
   "metadata": {},
   "source": [
    "Voici la matrice d'adjacence de $Q_3$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fccea987",
   "metadata": {},
   "outputs": [],
   "source": [
    "print_mat(cube(3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8404f708",
   "metadata": {},
   "source": [
    "Voici une vision sympa de la matrice d'adjacence de $Q_6$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e475167b",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (6, 6)\n",
    "A = cube(6)\n",
    "plt.imshow(A, cmap='hot', interpolation='bicubic')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3bfa34bf",
   "metadata": {},
   "source": [
    "### 7.4 Le lien avec le permanent"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bca878c",
   "metadata": {},
   "source": [
    "Soit $G=(S,A)$ un graphe. Notons $S=\\{x_0,\\ldots,x_{n-1}\\}$. À chaque couverture $\\mathcal C$ de $G$ par des cycles on peut associer la permutation $\\sigma\\in\\mathfrak S_n$ définie pour $i,j\\in\\bar n$ par $\\sigma(i)=j$ si et seulement si il existe un cycle de la couverture tel que $x_i\\rightarrow x_j$ dans ce cycle. On définit ainsi une application $F:\\mathcal C\\longmapsto\\sigma$ de l'ensemble des couvertures de $G$ vers $\\mathfrak S_n$. \n",
    "\n",
    "**Proposition.** $F$ est une injection.\n",
    "\n",
    "**Démonstration.** Preuve « facile ».\n",
    "\n",
    "**Proposition.** Soit $\\sigma\\in\\mathfrak S_n$. La permutation $\\sigma$ a un antécédent par $F$ si et seulement si pour tout $i\\in\\bar n$, $i\\rightarrow \\sigma(i)$ dans $G$. \n",
    "\n",
    "**Démonstration.** Par définition de $F$, cette condition est évidemment nécessaire. Inversement, supposons la condition réalisée. Décomposons $\\sigma=\\gamma_1\\ldots\\gamma_r$ en produit de cycles de supports disjoints $\\gamma_1,\\ldots,\\gamma_r$. Pour $k\\in[\\!|1, r|\\!]$, écrivons $\\gamma_k=(i_1\\ldots i_p)$. Le cycle (en tant que permutation) $\\gamma_k$ correspond à un cycle $\\Gamma_k=[i_1,\\ldots,i_p]$ (en tant que graphe) du graphe $G$. L'ensemble $\\mathcal C=\\{\\Gamma_1,\\ldots, \\Gamma_r\\}$ est alors une couverture de $G$ par des cycles, et $F(\\mathcal C)=\\sigma$. Ainsi, $\\sigma$ a un antécedent par $F$.\n",
    "\n",
    "Notons $A$ la matrice d'adjacence de $G$.\n",
    "\n",
    "**Corollaire.** Soit $\\sigma\\in\\mathfrak S_n$. La permutation $\\sigma$ a un antécédent par $F$ si et seulement si $\\prod_{i=0}^{n-1}A_{i\\sigma(i)}=1$.\n",
    "\n",
    "**Démonstration.** Par la proposition précédente, $\\sigma$ a un antécédent par $F$ si et seulement si pour tout $i\\in\\bar n$, $A_{i\\sigma(i)}=1$, ce qui équivaut à dire que le produit est égal à 1.\n",
    "\n",
    "**Corollaire.** Le nombre de couvertures de $G$ est $\\text{perm}(A)$.\n",
    "\n",
    "**Démonstration.** On a\n",
    "\n",
    "$$\\text{perm}(A)=\\sum_{\\sigma\\in\\mathfrak S_n}\\prod_{i=0}^{n-1}A_{i\\sigma(i)}$$\n",
    "\n",
    "Les termes de cette somme valent 0 ou 1. Ils valent 1 si et seulement si $\\sigma$ a un (unique) antécédent par $F$, d'où le résultat."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4da166a6",
   "metadata": {},
   "source": [
    "### 7.5 Retour aux exemples"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28260e5f",
   "metadata": {},
   "source": [
    "Nous pouvons maintenant revenir à nos exemples de graphes. Pour chacun d'entre-eux, déterminons le nombre de couvertures du graphe."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42dfddb1",
   "metadata": {},
   "source": [
    "#### 7.5.1 Graphes complets"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe4446f5",
   "metadata": {},
   "source": [
    "Tout d'abord, les graphes complets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa4db13b",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(11):\n",
    "    print(n, perm_ryser2(complet(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb0eaa09",
   "metadata": {},
   "source": [
    "La matrice d'adjacence du graphe complet $K_n$ est\n",
    "\n",
    "$$A_n=\\begin{pmatrix}0&1&1&\\ldots&1\\\\\n",
    "1&0&1&\\ldots&1\\\\\n",
    "\\vdots&\\vdots&\\vdots&&\\vdots\\\\\n",
    "1&1&1&\\ldots&0\n",
    "\\end{pmatrix}$$\n",
    "\n",
    "Érant donnée $\\sigma\\in\\mathfrak S_n$, on a $\\prod_{i=0}^{n-1}A_{i\\sigma(i)}=1$ si et seulement si pour tout $i\\in\\bar n$, $\\sigma(i)\\ne i$, c'est à dire lorsque $\\sigma$ est un *dérangement*. Sinon, ce produit est nul. Ainsi, $\\text{perm}(A)$ est le nombre de dérangements de $\\mathfrak S_n$. On peut ainsi démontrer (nous ne le ferons pas ici) que\n",
    "\n",
    "$$\\text{perm}(A_n)=n!\\sum_{k=0}^n\\frac{(-1)^k}{k!}$$\n",
    "\n",
    "Cette quantité équivaut, lorsque $n$ tend vers l'infini, à $\\frac 1 en!$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cc21d456",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_derangements(n):\n",
    "    s = 0\n",
    "    for k in range(n + 1):\n",
    "        s += (-1) ** k * math.factorial(n) // math.factorial(k)\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d3249f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(11):\n",
    "    print('%3d%10d%10d' % (n, perm_ryser2(complet(n)), nombre_derangements(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b31908a",
   "metadata": {},
   "source": [
    "#### 7.5.2 Cycles"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9633a30",
   "metadata": {},
   "source": [
    "Passons aux cycles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "145bd88a",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(2, 15):\n",
    "    print(n, perm_ryser2(cycle(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a88a2cdb",
   "metadata": {},
   "source": [
    "Par exemple, le nombre de couvertures de $C_6$ est égal à 4. En effet, les couvertures de $C_6$ sont\n",
    "\n",
    "- $\\{[0,1,2,3,4,5]\\}$.\n",
    "- $\\{[5,4,3,2,1,0]\\}$.\n",
    "- $\\{[0,1],[2,3],[4,5]\\}$.\n",
    "- $\\{[1,2],[3,4],[5,0]\\}$.\n",
    "\n",
    "On laisse au lecteur le soin de montrer que pour tout $n\\ge 3$,\n",
    "\n",
    "- Si $n$ est pair, $C_n$ possède 4 couvertures.\n",
    "- Si $n$ est impair, $C_n$ possède 2 couvertures."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c2b2a69",
   "metadata": {},
   "source": [
    "**Exercice.** Montrer que si $n$ est pair, le graphe $C_n$ est bipartite."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15c961e2",
   "metadata": {},
   "source": [
    "#### 7.5.3 Graphes bipartites complets"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec7438db",
   "metadata": {},
   "source": [
    "Voici le nombre de couvertures de $K_{n,n}$ pour $1\\le n\\le 9$. On affiche aussi dans la dernière colonne le nombre de mariages parfaits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "08b51272",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Knn(n):\n",
    "    G = n * [None]\n",
    "    for i in range(n):\n",
    "        G[i] = list(range(n))\n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "70f3f5b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(1, 10):\n",
    "    print('%3d%15d%15d' % (n, perm_ryser2(bipartite_complet(n)), perm_ryser2(matrice_biadjacence(Knn(n)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ea1f8f8",
   "metadata": {},
   "source": [
    "Cela ne saute peut-être pas aux yeux, mais les éléments de la dernière colonne sont les carrés de ceux de la colonne précédente. Pourquoi ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e5eaa10",
   "metadata": {},
   "source": [
    "**Proposition.** Soit $G$ un graphe bipartite. Soient $A$ la matrice d'adjacence de $G$ et $B$ sa matrice de biadjacence. On a\n",
    "\n",
    "$$\\text{perm}(A)=\\text{perm}(B)^2$$\n",
    "\n",
    "**Démonstration.** On a la décomposition par blocs\n",
    "\n",
    "$$A=\\begin{pmatrix}0&B\\\\ B^T&0\\end{pmatrix}$$\n",
    "\n",
    "Par des échanges de colonnes, le permanent de cette matrice est aussi celui de\n",
    "\n",
    "$$A'=\\begin{pmatrix}B&0\\\\ 0&B^T\\end{pmatrix}$$\n",
    "\n",
    "Nous avons vu que le permanent d'une matrice triangulaire est le produit de ses coefficients diagonaux. On peut en fait montrer que ce résultat s'étend à des matrices triangulaires par blocs, ce qui est le cas de $A'$. Ainsi,\n",
    "\n",
    "$$\\text{perm}(A)=\\text{perm}(A')=\\text{perm}(B)\\ \\text{perm}(B^T)=\\text{perm}(B)^2$$\n",
    "\n",
    "Remarquons que la matrice $B$ de biadjacence de $K_{n,n}$ ne contient que des 1. Ainsi, $\\text{perm}(B)=n!$. De là, le graphe $K_{n,n}$ possède $n!^2$ couvertures."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4fe9c7d",
   "metadata": {},
   "source": [
    "#### 7.5.4 Hypercubes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4db816f",
   "metadata": {},
   "source": [
    "Terminons par le nombre de couvertures des cubes. Attention, le nombre de sommets de $Q_n$ est $2^n$. Comme $2^5=32$ et que nous sommes incapables de calculer un permanent de taille 32 en moins de 16 heures, arrêtons-nous à $n=4$ ... pour l'instant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17b14a37",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(1, 5):\n",
    "    print(n, perm_ryser2(cube(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "580172ba",
   "metadata": {},
   "source": [
    "Le lecteur aura remarqué que les nombres de la dernière colonne sont des carrés. C'est en fait vrai pour **tout** $n\\ge 1$ :\n",
    "\n",
    "**Proposition.** Pour tout $n\\ge 1$, $Q_n$ est un graphe bipartite.\n",
    "\n",
    "**Démonstration.** Soit $S$ l'ensemble des sommets de $Q_n$. Écrivons $S=X\\cup Y$ où $X$ est l'ensemble des entiers $i\\in[\\!|0,2^n-1|\\!]$ ayant un nombre pair de bits égaux à 1 et $Y$ est l'ensemble des entiers $i\\in[\\!|0,2^n-1|\\!]$ ayant un nombre impair de bits égaux à 1. Avec notre définition de $Q_n$, il est immédiat que les arêtes de $Q_n$ ont pour extrémités un élément de $X$ et un élément de $Y$. Ainsi, $Q_n$ est bipartite.\n",
    "\n",
    "**Remarque.** Le lecteur est invité à montrer que $|X|=|Y|=2^{n-1}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b80cf75",
   "metadata": {},
   "source": [
    "Maintenant que nous savons que $Q_n$ est bipartite, nous pouvons obtenir le nombre de couvertures de $Q_5$. En effet, la matrice de biadjacence de $Q_5$ est de taille 16, taille tout à fait abordable pour un calcul de permanent avec la formule de Ryser.\n",
    "\n",
    "Avant tout, nous devons évidemment écrire une fonction qui renvoie la matrice de biadjacence en question. Le code ci-dessous est peu efficace mais suffira pour $n=5$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91d3aae3",
   "metadata": {},
   "source": [
    "Tout d'abord, la fonction `somme_bits` renvoie la somme des $n$ bits de l'entier $x\\in[\\!|0,2^n-1|\\!]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "140950d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def somme_bits(x, n):\n",
    "    return sum(bits(x, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0fea23fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "print([x for x in range(16) if somme_bits(x, 4) % 2 == 0])\n",
    "print([x for x in range(16) if somme_bits(x, 4) % 2 == 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca016201",
   "metadata": {},
   "source": [
    "La fonction `entier` prend en paramètre une liste $s=[b_0,\\ldots,b_{n-1}]$ de bits. Elle renvoie l'entier\n",
    "\n",
    "$$\\sum_{k=0}^{n-1}b_k2^k$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a96b52c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def entier(s):\n",
    "    n = len(s)\n",
    "    x = 0\n",
    "    for k in range(n):\n",
    "        x += s[k] * 2 ** k\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f053c2bc",
   "metadata": {},
   "source": [
    "Voici une fonction très mal écrite. `indice(x, s)` renvoie l'indice de l'objet $x$ dans la liste $s$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05bfbbe2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def indice(x, s):\n",
    "    i = 0\n",
    "    while s[i] != x: i = i + 1\n",
    "    return i"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8fe7b1fd",
   "metadata": {},
   "source": [
    "Enfin, la matrice de biadjacence du cube $Q_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cc299c0b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def matrice_biadjacence_cube(n):\n",
    "    A = matrice(2 ** (n - 1), 0)\n",
    "    xs = [x for x in range(2 ** n) if somme_bits(x, n) % 2 == 0]\n",
    "    ys = [x for x in range(2 ** n) if somme_bits(x, n) % 2 == 1]\n",
    "    for i in range(2 ** (n - 1)):\n",
    "        s = bits(xs[i], n)\n",
    "        for k in range(n):\n",
    "            s[k] = 1 - s[k]\n",
    "            y = entier(s)\n",
    "            j = indice(y, ys)\n",
    "            A[i][j] = 1\n",
    "            s[k] = 1 - s[k]\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00ad4b8e",
   "metadata": {},
   "source": [
    "Testons tout d'abord pour $n = 4$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9876e4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = matrice_biadjacence_cube(4)\n",
    "print(perm_ryser2(A) ** 2)\n",
    "print_mat(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47ed4ed2",
   "metadata": {},
   "source": [
    "Nous retrouvons pour $\\text{perm}(A)^2$ la valeur du permanent de la matrice d'adjacence de $Q_4$. \n",
    "\n",
    "Nous pouvons maintenant calculer le nombre de mariages parfaits et le nombre de couvertures de $Q_5$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53ca5a74",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = matrice_biadjacence_cube(5)\n",
    "p5 = perm_ryser2(A)\n",
    "print('Nombre de mariages parfaits :', p5)\n",
    "print('Nombre de couvertures       :', p5 ** 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64e57fd4",
   "metadata": {},
   "source": [
    "**Bilan :** le graphe  $Q_5$ possède environ 350 milliards de couvertures."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8fbc1236",
   "metadata": {},
   "source": [
    "Allons, terminons ce notebook par un dessin du graphe $Q_n$. Mais ce ne sera peut-être pas ce à quoi le lecteur s'attend ...\n",
    "\n",
    "Tout d'abord, voici une fonction qui renvoie le graphe bipartite $Q_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b1970a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def graphe_cube(n):\n",
    "    m = 2 ** (n - 1)\n",
    "    A = matrice_biadjacence_cube(n)\n",
    "    G = m * [None]\n",
    "    for i in range(m): G[i] = []\n",
    "    for i in range(m):\n",
    "        for j in range(m):\n",
    "            if A[i][j] == 1: G[i].append(j)\n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40bfbfa5",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(graphe_cube(3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "184659b5",
   "metadata": {},
   "source": [
    "Et maintenant, traçons $Q_5$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "133e87d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (8, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "382be142",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_graph(graphe_cube(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a88040ec",
   "metadata": {},
   "source": [
    "Peut-être vous attendiez-vous à voir un hypercube en dimension 5 ? Ce que nous voyons ici est **une** des façons de dessiner $Q_5$, celle qui met en évidence sa structure de graphe bipartite. Il existe de nombreuses façons de dessiner un graphe donné, chacune ayant ses avantages et ses inconvénients, mais ceci est un autre sujet ..."
   ]
  }
 ],
 "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": 5
}