{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.algo - la plus grande sous-s\u00e9quence croissante - correction\n", "\n", "Un exercice classique : trouver la plus grande sous-s\u00e9quence croissante. Celle-ci n'est pas n\u00e9cessairement un bloc contig\u00fc de la liste initiale mais les entiers apparaissent dans le m\u00eame ordre."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["L'algorithme optimal est expos\u00e9 en dernier, la correction propose un cheminement jusqu'\u00e0 cette solution en introduisant au fur et \u00e0 mesure les id\u00e9es qui aboutissent \u00e0 cette solution. A partir de la premi\u00e8re solution, on \u00e9lague peu \u00e0 peu :\n", "\n", "1. ce qu'il n'est pas n\u00e9cessaire de faire car math\u00e9matiquement inutile et ne changeant pas la solution,\n", "2. ce qu'il n'est pas n\u00e9cessaire de conserver d'une it\u00e9ration \u00e0 l'autre car cette information peut \u00eatre reconstruite et qu'il co\u00fbte plus cher de la stocker que de la reconstruire.\n", "\n", "$E[k]$, $E_k$ d\u00e9signent l'\u00e9l\u00e9ment d'indice $k$ de l'ensemble $E$. Sauf pr\u00e9cision contraire, il est tenu compte de l'ordre de tous les \u00e9l\u00e9ments dans l'ensemble auxquels ils appartiennent."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Solution simple\n", "\n", "Prenons un tableau quelconque :"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"text/plain": ["[10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9]"]}, "execution_count": 3, "metadata": {}, "output_type": "execute_result"}], "source": ["E = [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9] \n", "E"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Avant de passer \u00e0 l'algorithme dichotomique, on va d'abord suivre un chemin plus facile et plus lent. Supposons qu'on conna\u00eet la meilleure s\u00e9quence croissante de longueur $n : s (1 \\rightarrow n)$. \n", "\n", "On d\u00e9coupe cette s\u00e9quence en deux $s(1 \\rightarrow k)$ \n", "et $s(k+1 \\rightarrow n)$. \n", "On est s\u00fbr que la s\u00e9quence $s (1 \\rightarrow k)$ est la plus grande s\u00e9quence croissante incluant l'\u00e9l\u00e9ment $s_k$. \n", "Dans le cas contraire, on aurait trouv\u00e9 un moyen de fabriquer une plus longue s\u00e9quence croissante sur $E$. Et c'est contradictoire avec l'hypoth\u00e8se de d\u00e9part. \n", "\n", "A chaque indice $k$, il existe une meilleure s\u00e9quence $S[k]$ se terminant \u00e0 la position $k$ : $E[k]$ est le dernier \u00e9l\u00e9ment de la s\u00e9quence. On suppose que toutes les meilleures s\u00e9quences croissantes se terminant \u00e0 la position $i$ pour $i \\in [1:k]$. Comment calculer la meilleure s\u00e9quence croissante pour la position $i+1$ ? D'apr\u00e8s ce qui pr\u00e9c\u00e8de, il suffit de l'ajouter \u00e0 toutes les s\u00e9quences qui pr\u00e9c\u00e8dent puis de choisir la meilleure. Une fois qu'on a obtenu toutes les meilleures s\u00e9quences se terminant aux positions $i$, il suffit de prendre la plus longue."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/plain": ["('E',\n", " [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9],\n", " 'indice:',\n", " [4, 5, 6, 9, 10, 13],\n", " 'valeurs:',\n", " [2, 5, 7, 9, 15, 15])"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["def plus_grande_sequence_position_k(E, k=None):\n", " if k is None:\n", " k = len(E)-1\n", " if k == 0:\n", " return [[0]]\n", " else :\n", " S = plus_grande_sequence_position_k(E, k-1)\n", " \n", " best = []\n", " for j,s in enumerate(S):\n", " if len(s) > len(best) and E[k] >= E [s[-1]]:\n", " best = s \n", " best = best + [k]\n", " S.append(best) \n", " return S\n", " \n", "def plus_grande_sequence(E):\n", " if len(E) == 0:\n", " return E\n", " S = plus_grande_sequence_position_k(E)\n", " best = []\n", " for s in S:\n", " if len(s) > len(best):\n", " best = s\n", " return best\n", " \n", "b = plus_grande_sequence(E)\n", "\"E\",E,\"indice:\",b, \"valeurs:\", [ E[i] for i in b ]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le co\u00fbt de cet algorithme est en $O(n^2)$. L'\u00e9nonc\u00e9 de l'exercice sugg\u00e8re qu'on peut faire mieux en utilisant la dichotomie. En coupant l'ensemble $E$ en deux, $A=E (1 \\rightarrow k)$ et $B=E(1 \\rightarrow k+1)$, soit la plus grande s\u00e9quence croissante est dans $A$, soit dans $B$, soit elle commence avant la position $k$ et se termine apr\u00e8s. Les deux premiers cas sont tr\u00e8s simples \u00e0 traiter par r\u00e9currence. Le dernier l'est moins mais on sait deux choses : on cherche la s\u00e9quence $s (a \\rightarrow b)$ avec $a \\leqslant k \\leqslant b$ et la recherche de cette s\u00e9quence doit avant un co\u00fbt en $O(n)$ sinon le nouvel algorithme ne sera pas plus rapide que le pr\u00e9c\u00e9dent."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Solution simple am\u00e9lior\u00e9e\n", "\n", "Est-il n\u00e9cessaire de garder l'historique des s\u00e9quences ? Pour chaque position $k$, on conserve toute la meilleure s\u00e9quence se terminant \u00e0 la position $k$. Toutefois, il est possible de ne retenir que l'\u00e9l\u00e9ment pr\u00e9c\u00e9dent : $P[E[k]]$ car la meilleure s\u00e9quence $S[k]$ peut \u00eatre d\u00e9compos\u00e9e en $S[ E[k] ] + [ E[k] ]$. Cette am\u00e9lioration rentre dans la cat\u00e9gorie 2 : l'algorithme conserve une information non indispensable. \n", "\n", "La fonction est plus simple \u00e0 impl\u00e9menter de fa\u00e7on non r\u00e9cursive. Elle se sert de deux tableaux :\n", "\n", "- $longueur[k]$ : conserve la longueur de la meilleure s\u00e9quence se terminant \u00e0 la position $k$\n", "- $precedent[k]$ : conserve la position de l'\u00e9l\u00e9ment pr\u00e9c\u00e9dent dans la meilleure s\u00e9quence se terminant \u00e0 la position $k$ (donc pr\u00e9c\u00e9dent $k$)."]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"text/plain": ["('E',\n", " [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9],\n", " 'indice:',\n", " [4, 5, 6, 9, 10, 13],\n", " 'valeurs:',\n", " [2, 5, 7, 9, 15, 15])"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["def plus_grande_sequence_2(E):\n", " if len(E) == 0:\n", " return E\n", " \n", " precedent = [-1 for e in E]\n", " longueur = [0 for e in E]\n", " \n", " longueur[0] = 1\n", " for k in range(1, len(E)):\n", " \n", " bestL = 1\n", " bestP = -1\n", " \n", " for j in range(0,k) :\n", " if E[k] >= E [ j ] and longueur[j]+1 > bestL:\n", " bestL = longueur [j]+1\n", " bestP = j\n", " \n", " precedent[k] = bestP\n", " longueur[k] = bestL\n", " \n", " # on r\u00e9cup\u00e8re la longueur de la plus grande s\u00e9quence\n", " maxiL = 0\n", " for i,l in enumerate(longueur):\n", " if l > longueur[maxiL]:\n", " maxiL = i\n", " \n", " # on r\u00e9cup\u00e8re la plus grande s\u00e9quence\n", " seq = [maxiL]\n", " while precedent[seq[-1]] != -1:\n", " p = precedent[seq[-1]]\n", " seq.append(p)\n", " \n", " seq.reverse()\n", " return seq\n", " \n", "E = [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9] \n", "b = plus_grande_sequence_2(E)\n", "\"E\",E,\"indice:\",b, \"valeurs:\", [ E[i] for i in b ]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On compare les co\u00fbts. La seconde fonction est un peu plus rapide \u00e0 un facteur multiplicatif pr\u00e8s. Le co\u00fbt des deux fonctions est $O(n^2)$."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["n= 20\n", "89.9 \u00b5s \u00b1 18.2 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "38.8 \u00b5s \u00b1 3.08 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "n= 50\n", "324 \u00b5s \u00b1 41.6 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n", "186 \u00b5s \u00b1 21.5 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "n= 100\n", "1.18 ms \u00b1 94 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n", "653 \u00b5s \u00b1 125 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n", "n= 200\n", "4.86 ms \u00b1 715 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 100 loops each)\n", "2.24 ms \u00b1 148 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n"]}], "source": ["import random\n", "for n in (20,50,100,200) :\n", " E = [ random.randint(0,n) for i in range(n) ]\n", " print(\"n=\",n)\n", " %timeit plus_grande_sequence(E)\n", " %timeit plus_grande_sequence_2(E)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Un peu plus pr\u00e8s de la solution optimale\n", "\n", "La fonction pr\u00e9c\u00e9dente se termine par deux boucles. La premi\u00e8re d\u00e9termine la longueur de la plus longue s\u00e9quence, la seconde reconstruit la s\u00e9quence. Pour chaque $k$, on conserve la meilleure s\u00e9quence croissante se terminant \u00e0 la position $k$. Mais supposons que nous sommes \u00e0 l'it\u00e9ration $l$, et pour les positions $j < k < l$, et que les deux meilleures s\u00e9quences se terminant aux positions $k$ et $j$ ont m\u00eame longueur et que $E[k] < E[j]$, est-il vraiment n\u00e9cessaire de conserver une seconde s\u00e9quence aussi longue mais dont le dernier \u00e9l\u00e9ment est plus grand ?\n", "\n", "$\\begin{array}{|c|c|c|c|c|c|c|} \\hline & & & j & k & ... & l\\\\ \\hline S_j & 2 & 3 & 5 & && \\\\ \\hline S_k & 2 & 3 & & 4 && \\\\ \\hline \\end{array}$\n", "\n", "La r\u00e9ponse est \u00e9videmment non. Par extension, \u00e0 la position $l$, on peut classer toutes les s\u00e9quences se terminant avant :\n", "\n", "- par longueur d\u00e9croissante\n", "- par dernier \u00e9l\u00e9ment croissant\n", "\n", "Pour chaque longueur, on va conserver le plus petit dernier \u00e9l\u00e9ment possible parmi toutes les s\u00e9quences de cette longueur. L'optimisation est deux types : l'algorithme est plus rapide (son co\u00fbt est plus faible), il stocke moins d'information."]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"data": {"text/plain": ["('E',\n", " [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9],\n", " 'indice:',\n", " [4, 5, 6, 9, 15, 17],\n", " 'valeurs:',\n", " [2, 5, 7, 9, 11, 14])"]}, "execution_count": 7, "metadata": {}, "output_type": "execute_result"}], "source": ["def plus_grande_sequence_2L(E):\n", " if len(E) == 0:\n", " return E\n", " \n", " dernier = [0]\n", " precedent = [-1 for e in E]\n", " \n", " for k in range(1,len(E)):\n", " if E[k] >= E [dernier [-1]]:\n", " # on ajoute \u00e0 la derni\u00e8re s\u00e9quence\n", " precedent[k] = dernier[-1]\n", " dernier.append( k )\n", " else :\n", " # on s'en sert pour am\u00e9liorer une s\u00e9quence existante\n", " for j in range(len(dernier)-1, -1, -1):\n", " if E[k] < E [dernier[j]]:\n", " if precedent[dernier[j]] == -1:\n", " dernier [j] = k\n", " elif E[k] >= E[dernier[j-1]]:\n", " if j == 0:\n", " break\n", " precedent[k] = dernier[j-1] \n", " # ce n'est pas exactement precedent[dernier[j]],\n", " # mais cette valeur est admissible par construction\n", " dernier[j] = k\n", " break # car il ne sert \u00e0 rien d'aller plus loin\n", " \n", " \n", " # on r\u00e9cup\u00e8re la plus grande s\u00e9quence\n", " seq = [dernier[-1]]\n", " while precedent[seq[-1]] != -1:\n", " p = precedent[seq[-1]]\n", " seq.append(p)\n", " \n", " seq.reverse()\n", " return seq\n", " \n", "E = [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9] \n", "b = plus_grande_sequence_2L(E)\n", "\"E\",E,\"indice:\",b, \"valeurs:\", [ E[i] for i in b ]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On compare les co\u00fbts. La seconde fonction est un peu plus rapide \u00e0 un facteur multiplicatif pr\u00e8s. Le co\u00fbt de la premi\u00e8re fonction est en $O(n^2)$. La seconde est en $O(nL)$ o\u00f9 $L$ est la longueur de la plus longueur s\u00e9quence. On majore ce co\u00fbt par $O(n^2)$ mais dans les faits, c'est plus court."]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["37.9 \u00b5s \u00b1 5.51 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "19.3 \u00b5s \u00b1 2.62 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "162 \u00b5s \u00b1 8.65 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "76.5 \u00b5s \u00b1 4.98 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "568 \u00b5s \u00b1 25.1 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n", "137 \u00b5s \u00b1 2.8 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "2.27 ms \u00b1 192 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 100 loops each)\n", "357 \u00b5s \u00b1 57.8 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n"]}], "source": ["import random\n", "for n in (20,50,100,200) :\n", " E = [random.randint(0,n) for i in range(n)]\n", " %timeit plus_grande_sequence_2(E)\n", " %timeit plus_grande_sequence_2L(E)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Solution optimale\n", "\n", "Enfin, la solution propos\u00e9e sur la page [wikipedia](http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms). Elle consiste simplement \u00e0 remplacer la boucle imbriqu\u00e9e par une recherche dichotomique. En effet, on cherche le premier \u00e9l\u00e9ment plus petit qu'un autre dans un tableau tri\u00e9. Cela peut \u00eatre ais\u00e9ment remplac\u00e9 par une recherche dichotomique. Les paragraphes qui suivent reprennent l'explication depuis le d\u00e9but avec les notations de l'article [wikipedia](http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms).\n", "\n", "L'id\u00e9e consiste \u00e0 parcourir le tableau de gauche \u00e0 droite en conservant \u00e0 chaque it\u00e9ration des s\u00e9quences optimales de longueur $1$ \u00e0 $L$ en s'assurant que chaque s\u00e9quence se termine par le plus petit entier possible.\n", "\n", "L'impl\u00e9mentation s'appuie sur un tableau $M_{1 \\rightarrow n}$. La variable $L$ m\u00e9morise la longueur de la plus grande s\u00e9quence connue jusque l\u00e0. A l'it\u00e9ration $i$, $M[L]$ contient l'indice du dernier \u00e9l\u00e9ment de la meilleure s\u00e9quence croissante de longueur $L$ dans l'ensemble $E (1 \\rightarrow i)$. $M[k]$ pour $1 \\leqslant i \\leqslant i$ contient l'indice du dernier \u00e9l\u00e9ment d'une s\u00e9quence de $k$ nombre compris entre les indices $1$ et $i$.\n", "\n", "A chaque it\u00e9ration $i+1$, on met \u00e0 jour le tableau $M$ en consid\u00e9rant l'\u00e9l\u00e9ment $E[i+1]$. Tout d'abord, si $E[i+1] \\geqslant E[ M[L]]$, cela veut dire qu'on peut ajouter l'\u00e9l\u00e9ment $E[i+1]$ \u00e0 la plus grande s\u00e9quence connue, elle sera n\u00e9cessairement la plus grande. Si maintenant $E[i+1] < E[ M[L]]$, il n'y aura pas de meilleure s\u00e9quence. Pour autant, cet \u00e9l\u00e9ment remplacera le dernier \u00e9l\u00e9ment d'une s\u00e9quence de longueur moindre s'il est plus petit. On peut ais\u00e9ment comprendre cela : si deux s\u00e9quences ont m\u00eame longueur, celle se terminant par le plus petit \u00e9l\u00e9ment a plus de chance de s'agrandir par la suite.\n", "\n", "L'algorithme repose sur une propri\u00e9t\u00e9 du tableau $M$ : la suite $E[M[i]]$ est croissante entre $1$ et $L$. On peut dire cela autrement : il existe une s\u00e9quence de longueur $L-1$ dont le dernier \u00e9l\u00e9ment est n\u00e9cessaire plus petit que le dernier \u00e9l\u00e9ment de la meilleure s\u00e9quence de longueur $L$. Il suffit que prend les $L-1$ premiers \u00e9l\u00e9ments de la meilleure s\u00e9quence de longueur $L$."]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"data": {"text/plain": ["('E',\n", " [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9],\n", " '...',\n", " 'indice:',\n", " [4, 5, 6, 9, 15, 17],\n", " 'valeurs:',\n", " [2, 5, 7, 9, 11, 14])"]}, "execution_count": 9, "metadata": {}, "output_type": "execute_result"}], "source": ["def plus_grande_sequence_wikipedia(E):\n", " P = [-1 for _ in E]\n", " M = [-1 for _ in E]\n", "\n", " L = 0\n", " for i in range(0, len(E)):\n", " lo = 1\n", " hi = L\n", " while lo <= hi:\n", " mid = (lo + hi) // 2\n", " if E[M[mid]] < E[i]:\n", " lo = mid + 1\n", " else:\n", " hi = mid - 1\n", "\n", " newL = lo\n", " P[i] = M[newL - 1]\n", "\n", " if newL > L:\n", " M[newL] = i\n", " L = newL\n", " elif E[i] < E[M[newL]]:\n", " M[newL] = i\n", "\n", " S = [-1 for i in range(L)]\n", " k = M[L]\n", " for i in range(L-1, -1, -1) :\n", " S[i] = k\n", " k = P[k]\n", "\n", " return S\n", "\n", "E = [10, 15, 7, 19, 2, 5, 7, 16, 3, 9, 15, 0, 1, 15, 6, 11, 0, 14, 7, 9] \n", "b = plus_grande_sequence_wikipedia(E)\n", "\"E\",E,\"...\",\"indice:\",b, \"valeurs:\", [ E[i] for i in b ]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On compare avec la version pr\u00e9c\u00e9dente et on v\u00e9rifie qu'elle est plus rapide."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["n= 20\n", "21.9 \u00b5s \u00b1 1.46 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "15.8 \u00b5s \u00b1 877 ns per loop (mean \u00b1 std. dev. of 7 runs, 100000 loops each)\n", "n= 50\n", "60.3 \u00b5s \u00b1 4.66 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "42.9 \u00b5s \u00b1 3.38 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "n= 100\n", "127 \u00b5s \u00b1 4.52 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "102 \u00b5s \u00b1 9.96 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n", "n= 200\n", "411 \u00b5s \u00b1 42.4 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n", "228 \u00b5s \u00b1 15 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n"]}], "source": ["import random\n", "for n in (20,50,100,200) :\n", " E = [ random.randint(0,n) for i in range(n) ]\n", " print(\"n=\",n)\n", " %timeit plus_grande_sequence_2L(E)\n", " %timeit plus_grande_sequence_wikipedia(E)"]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "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.7.2"}}, "nbformat": 4, "nbformat_minor": 2}