{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Énumération des parties d'un ensemble\n",
    "\n",
    "Marc Lorenzi\n",
    "\n",
    "2 avril 2023"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (8, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considérons le problème suivant. On se donne une liste $[x_1,\\ldots,x_n]$ d'entiers et un entier $t$. Existe-t-il un ensemble $A\\subseteq[|1,n|]$ tel que \n",
    "\n",
    "$$\\sum_{i\\in A} x_i=t \\ ?$$\n",
    "\n",
    "Ce problème est appelé **SUBSET SUM**. Une méthode évidente pour le résoudre est de considérer une à une toutes les parties $A$ de $[|1,n|]$ et de regarder si l'une d'entre elles répond à la question.\n",
    "\n",
    "Peut-on faire mieux ? La réponse est « non, pas vraiment », du moins en l'état de nos connaissances. Le problème **SUBSET SUM** fait partie d'une classe de problèmes appelée la classe **NP**. Pour faire simple, il est facile, si je vous donne un ensemble $A$, de vérifier qu'il convient. Voici d'ailleurs la fonction qui répond à la question (en supposant que $A$ est bien une partie de $E$, ce que l'on pourrait aussi vérifier en temps raisonnable) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_subset(E, t, A):\n",
    "    return sum(A) == t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "E = [19, 13, 4, 6, 12, 7, 7, 10, 2, 15, 19, 4, 19, 2, 11, 19, 18, 6, 8, 19]\n",
    "check_subset(E, 110, [19, 13, 6, 12, 7, 7, 10, 2, 15, 19])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La classe **NP** est la classe des problèmes pour lesquels il est facile de vérifier en « temps raisonnable » (raisonnable signifiant, pour faire vite,  polynomial en la taille de l'entrée) une solution que l'on nous a donnée. Il se trouve qu'un certain nombre de problèmes de cette classe sont plus importants que les autres. Si on sait **résoudre** l'un de ces problèmes en temps raisonnable alors ont sait résoudre **tous** les problèmes de la classe **NP** en temps raisonnable. Ces problèmes sont dits NP-complets. Il s'avère que **SUBSET_SUM** est NP-complet. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le but de ce notebook est apparemment d'écrire une fonction qui résout **SUBSET SUM**. En réalité, ce qui m'intéresse c'est de parler de *codes de Gray*. La fonction que nous allons écrire sera de complexité exponentielle, bien évidemment. Sinon, nous serions en première ligne pour la médaille Fields. L'idée sera naïve : énumérer toutes les parties de l'ensemble $E$, calculer la somme des éléments de la partie. Si la somme est $t$, renvoyer la partie en question.\n",
    "\n",
    "Clairement, nous sommes ramenés au problème suivant : comment énumérer aussi efficacement que possible toutes les parties d'un ensemble ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. L'approche récursive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $E$ un ensemble. Si $E$ est vide, il n'a qu'une partie : l'ensemble vide. Sinon, soit $x$ un élément de $E$. Soit $E'=E\\setminus\\{x\\}$. Les parties de $E$ sont les parties de $E'$, ainsi que les parties de $E'$ auxquelles on rajoute $x$. D'où, immédiatement, une fonction récursive qui résout la question."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def liste_parties(E):\n",
    "    if len(E) == 0: return [[]]\n",
    "    else:\n",
    "        P1 = liste_parties(E[1:])\n",
    "        return P1 + [[E[0]] + A for A in P1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(liste_parties(list(range(5))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si on réfléchit un peu on voit apparaître quelques inconvénients. On calcule toutes les parties de $E$ et on les stocke dans une énorme liste. Cette fonction est donc non seulement de complexité exponentielle en temps mais aussi de complexité exponentielle en espace. De combien d'espace a-t-on besoin pour stocker la liste des parties de $E$ ? Soit $n=|E|$, le cardinal de $E$. Pour $0\\le k\\le n$, il y a $\\binom n k$ parties de cardinal $k$, qui contiennent donc au total $k\\binom n k$ éléments. Il reste à sommer sur $k$ pour obtenir un total de \n",
    "\n",
    "$$X_n=\\sum_{k=0}^nk\\binom n k$$\n",
    "\n",
    "objets à stocker. Que vaut $X_n$ ? Pour $1\\le k\\le n$, on a $\\frac k n \\binom n k = \\binom {n-1}{k-1}$. Donc \n",
    "\n",
    "$$X_n=n\\sum_{k=1}^n\\frac k n \\binom n k=n\\sum_{k=1}^n\\binom {n-1} {k-1}$$\n",
    "\n",
    "Le changement d'indice $k'=k-1$ donne \n",
    "\n",
    "$$X_n=n\\sum_{k=0}^{n-1}\\binom {n-1} {k}=n2^{n-1}$$\n",
    "\n",
    "C'est vraiment très gros. Pour $n=20$ cela fait environ 10 millions d'objets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "20 * 2 ** 19"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Fonction indicatrice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tentons une autre approche. Une partie de la liste $[x_1,\\ldots,x_n]$ est caractérisée par les indices des $x_i$ que nous voulons mettre dans cette partie. Ou, si l'on préfère, par un $n$-uplet $[\\varepsilon_1,\\ldots,\\varepsilon_n]$ où $\\varepsilon_i= 0$ ou 1. Lorsqu'il vaut 1, on prend le $x_i$ correspondant. Lorsqu'il vaut 0 on ne prend pas. Mais un tel $n$-uplet de 0 et de 1 peut être interprété comme la représentation binaire d'un entier entre 0 et $2^n-1$. Énumérer les parties de $E$ c'est donc énumérer les entiers entre 0 et $2^n-1$. Et ça c'est très facile. Il faut juste écrire quelques fonctions de conversion. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `int_to_bin` prend deux entiers $k$ et $n$ en paramètres. Elle renvoie la représentation sur $n$ bits de l'entier $k$, avec les bits de poids faible sur la gauche. Si vous préférez le contraire il n'y a qu'à faire un renversement de liste. La complexité temporelle de `int_to_bin` est clairement $O(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def int_to_bin(k, n):\n",
    "    s = []\n",
    "    for i in range(n):\n",
    "        s.append(k % 2)\n",
    "        k = k // 2\n",
    "    # s.reverse()\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "int_to_bin(78, 12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `indic` prend en paramètres un ensemble $E$ à $n$ éléments et une liste $c$ de bits. Elle renvoie le sous-ensemble de $E$ correspondant. Ici encore, si $E$ est de cardinal $n$, nous avons une complexité temporelle en $O(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def indic(E, c):\n",
    "    F = [] \n",
    "    for k in range(len(E)):\n",
    "        if c[k] == 1:\n",
    "            F.append(E[k])\n",
    "    return F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "indic([0,1,2,3,4], [0,1,1,0,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est maintenant facile d'énumérer les parties de $E$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parties0(E):\n",
    "    n = len(E)\n",
    "    for k in range(2 ** n):\n",
    "        yield indic(E, int_to_bin(k, n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que fait `yield`? Nous venons en fait de créer ce que l'on appelle un générateur. Exactement comme on peut écrire `for i in range(10): ...` ou `for x in s: ...` nous pouvons maintenant écrire la ligne `for P in parties0([1, 2, 3]): ...`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for P in parties0([1, 2, 3, 4, 5]): print(P, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Remarque.** Si $E$ est un ensemble de cardinal $n$, la complexité spatiale de l'énumération des parties de $E$ est en $O(n)$ et la complexité temporelle en $O(n2^n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ci-dessous, un graphique représentant la taille des parties de $E$ dans l'ordre où elles sont énumérées. À chaque étape, on ne peut monter que de 1, mais on peut redescendre beaucoup ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 8\n",
    "s = [len(p) for p in parties0(list(range(n)))]\n",
    "plt.plot(s, '--k', lw=1)\n",
    "plt.plot(s, 'or', ms=3)\n",
    "plt.axis([0, 2 ** n, 0, n])\n",
    "plt.grid()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Codes de Gray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Qu'est-ce qu'un code de Gray ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Définition.** Soit $n\\in\\mathbb N$. Un *code de Gray* de taille $n$ est une énumération de tous les $n$-uplets de bits (i.e. 0 ou 1) telle que l'on passe d'un $n$-uplet au suivant en changeant la valeur d'un unique bit. Un tel code est *cyclique* lorsque, de plus, on passe du dernier $n$-uplet au premier en changeant aussi un unique bit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Par exemple, un code de Gray cyclique de taille 2 est : 00, 10, 11, 01. Un code de Gray cyclique de taille 3 est 000, 100, 110, 010, 011, 111, 101, 001. Il existe de nombreuses familles de codes de Gray, et de nombreuses applications de ceux-ci. Nous allons nous intéresser aux codes de Gray dits cycliques réflexifs.\n",
    "\n",
    "Si vous voulez une vision concrète d'un code de Gray, dessinez un cube dont les côtés ont pour coordonnées 0 ou 1. Les 8 sommets du cube ont pour coordonnées les éléments d'un code de Gray de taille 3. Puis parcourez les sommets de ce cube en partant de $[0,0,0]$ et en prenant les éléments successifs du code de Gray. Comme un seul bit est changé à chaque étape, on suit les arêtes du cube. On passe une et une seule fois par chaque sommet, et puis on revient au point de départ parce que le code est cyclique. On vient de faire un **parcours hamiltonien** du cube.\n",
    "\n",
    "*En résumé* : un code de Gray cyclique de taille $n$ est un cycle hamiltonien de l'hypercube en dimension $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Créer des codes de Gray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Supposons créé un code de Gray de taille $n$ tel que le premier $n$-uplet (le zéroième plutôt) soit \n",
    "\n",
    "$$c_0=[0,\\ldots,0]$$\n",
    "\n",
    "et le dernier (le $2^n-1$-ième, donc) soit \n",
    "\n",
    "$$c_{2^n-1}=[0,\\ldots,0, 1]$$\n",
    "\n",
    "Pour $i=0,\\ldots 2^n-1$, soit \n",
    "\n",
    "- $c'_i=c_i$ auquel on rajoute un 0 à la fin, et \n",
    "- $c''_i=c_i$ auquel on rajoute un 1 à la fin. \n",
    "\n",
    "Il est alors clair que la suite $c'_0,\\ldots,c'_{2^n-1},c''_{2^n-1},\\ldots,c''_0$ est un code de Gray cyclique de taille $n+1$ dont le premier code est $[0,\\ldots,0]$ et le dernier est $[0,\\ldots,0, 1]$. Aux soins du lecteur de vérifier les petits détails (le passage du dernier « prime » au premier « seconde » , le renversement d'un code de Gray en est-il encore un, etc.).\n",
    "\n",
    "Nous venons de montrer par récurrence sur $n$ que la fonction ci-dessous renvoie, pour tout $n$, un code de Gray cyclique de taille $n$ dont le premier et le dernier élément sont $[0,\\ldots,0]$ et $[0,\\ldots,0, 1]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def liste_gray(n):\n",
    "    if n == 0: return [[]]\n",
    "    else:\n",
    "        g1 = liste_gray(n - 1)\n",
    "        g2 = g1[:]\n",
    "        g2.reverse()\n",
    "        return [c + [0] for c in g1] + [c + [1] for c in g2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(liste_gray(3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "D'où une nouvelle fonction qui renvoie la liste des parties d'un ensemble $E$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parties1(E):\n",
    "    p = len(E)\n",
    "    return [indic(E, c) for c in liste_gray(p)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(parties1([1, 2, 3, 4, 5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cela dit, il semblerait que nous soyons revenus au point de départ : la fonction qui renvoie les codes de Gray occupe un espace mémoire exponentiel. Ce qu'il faudrait, c'est trouver une formule magique qui fait passer d'un code de Gray au suivant, sans rien stocker à part le code et son numéro d'ordre. Regardons d'un peu plus près quel est le bit qui est changé à chaque étape."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Énumérer les codes de Gray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(liste_gray(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour le code à 4 bits, voici la liste des numéros du bit qui est changé pour passer du $i-1$ème code au $i$ème, $i=1,2,\\ldots,15$ :\n",
    "\n",
    "$$\\begin{array}{cccccccccccccccc}\n",
    "i&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\\\n",
    "b&0&1&0&2&0&1&0&3&0&1&0&2&0&1&0\\\\\n",
    "\\end{array}$$\n",
    "\n",
    "Pour tout entier $i\\ge 1$, notons $\\nu_2(i)$ la *valuation dyadique* de $i$, c'est à dire le plus grand entier $k$ tel que $2^k$ divise $i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Proposition.** pour tout entier $n\\ge 1$, pour tout $i$ entre 1 et $2^n-1$, on passe du $(i-1)$-ième code de Gray au $i$-ième code de Gray en modifiant le $\\nu_2(i)$-ème bit du code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Démonstration.** On fait une récurrence sur $n$. Pour $n=1$, c'est évident. Soit $n\\ge 1$. Supposons la propriété vraie pour $n$. Soit $1\\le i\\le 2^{n+1}-1$. Il y a 3 cas à considérer :\n",
    "\n",
    "- $1\\le i \\le 2^n-1$ : le $i$-ème code de gray de taille $n+1$ est le $i$-ème de code de taille $n$ auquel on a rajouté un 0 à la fin. De même pour le $i-1$-ième. L'hypothèse de récurrence s'applique directement.\n",
    "- $i = 2^n$ : c'est le dernier bit, c'est à dire le bit $n$ qui est modifié pour passer du $(i-1)$-ième code au $i$-ième. Cela tombe bien puisque $\\nu_2(2^n)=n$.\n",
    "- $2^n+1\\le i \\le 2^{n+1}-1$ : là on se trouve dans la deuxième moitié de la liste, qui est la liste ___inversée___ des codes de taille $n$ auxquels on a rajouté un 1. Il faut donc se demander comment on passe du $i'+1$-ième code de taille $n$ au $i'$-ième code de taille $n$, où $i'=2^{n+1}-i-1$. Inverser un bit est une opération involutive, donc par l'hypothèse de récurrence, cela se fait en changeant le bit numéro $\\nu_2(i'+1)$. Mais $\\nu_2(i'+1)=\\nu_2(2^{n+1}-i)=\\nu_2(i)$, car $i < 2^{n+1}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant c'est facile. La fonction `nu2` renvoie $\\nu_2(n)$, où $n$ est censé être un entier naturel non nul."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nu2(n):\n",
    "    c = 0\n",
    "    while n % 2 == 0:\n",
    "        c += 1\n",
    "        n = n // 2\n",
    "    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([nu2(i) for i in range(1, 16)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `next` prend un couple $u=(c,n)$ en paramètre, où $c$ est le $n$ième code de Gray. Elle renvoie $(c',n+1)$ où $c'$ est le $(n+1)$-ième code de Gray."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def next(u):\n",
    "    c, n = u\n",
    "    j = nu2(n + 1)\n",
    "    c [j] = 1 - c[j]\n",
    "    return (c, n + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "u = ([0, 0, 0, 0], 0)\n",
    "print(u)\n",
    "for k in range(15):\n",
    "    u = next(u)\n",
    "    print(u)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Un générateur de codes de Gray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `gray` ci-dessous prend un paramètre $n$ en entrée. Elle initialise une variable `code` au $n$-uplet qui ne contient que des zéros. Puis elle effectue $2^n-1$ fois le calcul de l'élément suivant du code de Gray, qu'elle place dans la variable `code`. Bref, elle énumère les codes de Gray."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gray(n):\n",
    "    code = n * [0]\n",
    "    yield code\n",
    "    for k in range(1, 2 ** n):\n",
    "        j = nu2(k)\n",
    "        code[j] = 1 - code[j]\n",
    "        yield code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for c in gray(3): print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La complexité temporelle de l'énumération des codes de Gray est bien entendu exponentielle. On n'y peut rien, un ensemble de cardinal $n$ a $2^n$ parties. Une majoration naïve de la complexité  nous dit que `nu2` prend en pire cas  un temps de l'ordre de $n$ pour calculer la valuation dyadique d'un entier $k\\le 2^n$. La complexité en temps de l'énumération des codes de Gray est donc un $O(n2^n)$.\n",
    "\n",
    "En fait, c'est mieux que cela. Le nombre d'opérations nécessaires au calcul de $\\nu_2(k)$ est ... $\\nu_2(k)$. Le nombre total d'opérations effectuées est ainsi\n",
    "\n",
    "$$C_n=\\sum_{k=1}^{2^n-1}\\nu_2(k)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Proposition.** $C_n=2^n-n-1$.\n",
    "\n",
    "**Démonstration.** Pour tout $i\\in[|0,n-1|]$, soit\n",
    "\n",
    "$$A_i=\\{k\\in[|1,2^n-1|]:\\nu_2(k)=i\\}$$\n",
    "\n",
    "On a alors\n",
    "\n",
    "$$C_n=\\sum_{i=0}^{n-1} i|A_i|$$\n",
    "\n",
    "Quels est le cardinal de $A_i$ ? Soit $k\\in[|1,2^n-1|]$. On a $k\\in A_i$ si et seulement si il existe $p\\in\\mathbb N$ tel que $k=2^i(2p+1)$ et\n",
    "\n",
    "$$2^i(2p+1)< 2^n$$\n",
    "\n",
    "ou encore\n",
    "\n",
    "$$p< 2^{n-i-1} -\\frac 1 2$$\n",
    "\n",
    "Comme $p$ est entier, ceci équivaut à \n",
    "\n",
    "$$0\\le p< 2^{n-i-1}$$\n",
    "\n",
    "Ainsi, pour tout $i\\in[|0, n-1|]$, $|A_i|=2^{n-i-1}$. De là,\n",
    "\n",
    "$$C_n=\\sum_{i=0}^{n-1} i2^{n-i-1}$$\n",
    "\n",
    "On vérifie alors facilement par récurrence sur $n$ que $C_n=2^n-n-1$.\n",
    "\n",
    "Finalement, la complexité temporelle de l'énumération des codes de Gray est un $O(2^n)$. Sachant qu'il y a $2^n$ codes, on peut difficilement faire mieux !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def complexite_gray(n):\n",
    "    s = 0\n",
    "    for k in range(1, 2 ** n):\n",
    "        s += nu2(k)\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(11):\n",
    "    print('%3d%5d%5d' % (n, complexite_gray(n), 2 ** n - n - 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Parties de $E$, version définitve"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 Le code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Écrire un générateur des parties d'un ensemble est maintenant immédiat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parties(E):\n",
    "    for c in gray(len(E)):\n",
    "        yield indic(E, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for p in parties(range(6)): print(p, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant, chaque partie renvoyée par le générateur a un rapport simple avec la précédente et la suivante."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 8\n",
    "s = [len(p) for p in parties(list(range(n)))]\n",
    "plt.plot(s, '--k', lw=1)\n",
    "plt.plot(s, 'or', ms=3)\n",
    "plt.axis([0, 2 ** n, 0, n])\n",
    "plt.grid()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si $E$ est un ensemble de cardinal $n$, la fonction `indic` prend un temps de l'ordre de $n$ pour créer un ensemble à partir d'une liste de 0 et de 1. Le temps cumulé de la création de toutes les parties de $E$ se fait donc en temps $O(n2^n)$. Nous avons déjà vu que le temps cumulé du calcul des $\\nu_2(k)$ est un $O(2^n)$. Ainsi, l'énumération de toutes les parties de $E$ a une complexité temporelle en $O(n2^n)$.\n",
    "\n",
    "Qu'en est-il de la complexité en espace ? Mis à part l'espace utilisé par $E$, il faut uniquement de l'espace pour stocker la variable `code`, qui est une liste de $n$ bits, plus un espace constant pour les variables restantes. La complexité en espace est donc en $O(n)$ où $n$ est le nombre d'éléments de $E$.\n",
    "\n",
    "Résumons nous. Pour un ensemble de cardinal $n$,\n",
    "\n",
    "- La complexité temporelle de l'énumération est $O(n2^n)$.\n",
    "- La complexité spatiale de l'énumération est $O(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. __SUBSET SUM__ en trois lignes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `subset_sum` est maintenant évidente. Sa complexité en pire cas est exponentielle. Cela survient en particulier lorsque le problème n'a pas de solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def subset_sum(E, t):\n",
    "    for p in parties(E):\n",
    "        if sum(p) == t: return (True, p)\n",
    "    return (False, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "E = [random.randint(1, 10) for k in range(20)]\n",
    "print(E)\n",
    "print(subset_sum(E, 32))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}