{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "checksum": "0050af0d277b1f77c4f7923aa4e17257",
     "grade": false,
     "grade_id": "cell-fa9f824efeef5775",
     "locked": true,
     "schema_version": 1,
     "solution": false
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Les ensembles (set)\n",
    "\n",
    "> Découverte de la structure d'ensembles en Python\n",
    "\n",
    "- toc: true\n",
    "- badges: true\n",
    "- comments: false\n",
    "- categories: [python, ISN]\n",
    "\n",
    "Un ensemble en python (***set***) est une structure pouvant contenir plusieurs données, mais contrairement aux listes, ces données sont uniques et non ordonnées. Il n'y a pas de moyen d'accéder à une donnée en particulier en utilisant son numéro d'index.\n",
    "\n",
    "Les ensembles sont par contre extrèmement efficaces pour la recherche d'un élément : Contrairement aux listes dans lesquelles une recherche impose de parcourir tous les éléments, les ensembles utilisent des techniques d'optimisation (table de hachage) rendant la recherche très performante.\n",
    "\n",
    "Voici quelques illustrations de l'utilisation des ***set***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "c251bc59ad41c282d2c928a145d1335e",
     "grade": false,
     "grade_id": "cell-824820d74bee6fc4",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# créer un un ensemble\n",
    "\n",
    "ensemble = {1,5,9,5,1,2,4}\n",
    "ensemble"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9f369e266cf9fdc337df011cf365000c",
     "grade": false,
     "grade_id": "cell-6be3334c0e3484d1",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Comme on peut le voir, les éléments en doubles dans *ensemble* ont été éliminés et l'ordre affiché n'est pas celui dans lequel les éléments ont été saisis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "789e6978834ca802dd02921a037f264a",
     "grade": false,
     "grade_id": "cell-5287a4a49989c2e3",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# essayons quelque chose...\n",
    "\n",
    "ensemble[3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "351be16c5736f5848759a62026ca7c29",
     "grade": false,
     "grade_id": "cell-4bca9c5408ea16b1",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "l'accès aux éléments par indice comme pour les listes n'est pas possible, cela n'a tout simpliement pas de sens.\n",
    "\n",
    "## Conversion list <-> set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "e3dea507a80de916c55ab0f37356003b",
     "grade": false,
     "grade_id": "cell-3e753b73742fd7f2",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "liste = [1,5,9,5,1,2,4]\n",
    "ensemble = set(liste)\n",
    "ensemble"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "efa0acd46c04c3d45f4d365a5cea83ef",
     "grade": false,
     "grade_id": "cell-00873144e498249e",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "ensemble = {1, 9, 5, 4, 2}\n",
    "liste = list(ensemble)\n",
    "liste"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "6ac1d632439012085cda4dade8e1d748",
     "grade": false,
     "grade_id": "cell-09a8f00754bf173c",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Méthodes sur les ensembles\n",
    "\n",
    "### ajout et retrait : add et remove"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "98889ebb682b7895c6a0410716c8240c",
     "grade": false,
     "grade_id": "cell-7e68e859d16318cb",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "ensemble = {1, 9, 5, 4, 2}\n",
    "ensemble.add(18)\n",
    "ensemble.remove(9)\n",
    "ensemble"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a42de61ced835f356682db5da0a2e1da",
     "grade": false,
     "grade_id": "cell-c9d0d7b1f2d772df",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Attention de bien tester si un élément est dans l'ensemble avant la suppression car sinon..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "faa2106a522bc7aee07b8e2a180d2ef6",
     "grade": false,
     "grade_id": "cell-5db9d63ffd416f43",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "ensemble.remove(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "7fb37846ecc79e6c1ebc8ec094879661",
     "grade": false,
     "grade_id": "cell-f6cfd0aefd0813ff",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "et du coup ...\n",
    "### tester si un élément est présent dans un ensemble : in"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a9c8ee4ccb8dc9499b1b5768fc8af118",
     "grade": false,
     "grade_id": "cell-0dfcd8552ff25a5e",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "3 in ensemble"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ef64e739d5d2d0a204b9fc8f794d86fd",
     "grade": false,
     "grade_id": "cell-508a86870e4770a1",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "18 in ensemble"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "e0c983b6622340aae6d711f8bb6c8656",
     "grade": false,
     "grade_id": "cell-31a88684b9e89b36",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Longueur et ensemble vide"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8c0a1114673641f2a05c3a3fb58a581c",
     "grade": false,
     "grade_id": "cell-a55210fe95b8297d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# l'ensemble vide est noté {} ou set()\n",
    "vide = set()\n",
    "vide.add(3)\n",
    "vide.remove(3)\n",
    "\n",
    "# Calculer le nb d'éléments d'un ensemble\n",
    "len(vide)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "59e929c992159f2775cdb470e0272aba",
     "grade": false,
     "grade_id": "cell-74d95da6d9605a19",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Application\n",
    "Créer une fonction **ensembleCarres** prenant en paramètre un entier $n$ e renvoyant un ensemble contenant les carrés des entiers de 1 à $n$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "d365865ae4fe786ec41db61a74ff7e28",
     "grade": false,
     "grade_id": "cell-95cadc4f89194224",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def ensembleCarres(n):\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "dce26661d79197c7415d474be66d3ff5",
     "grade": true,
     "grade_id": "cell-052d63ccbf55abb4",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "ec = ensembleCarres(10)\n",
    "assert len(ec)==10\n",
    "assert 64 in ec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "2fc7a56cf22734749b24711d3b05c17d",
     "grade": false,
     "grade_id": "cell-d0a5ab370d23b225",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "- Créez une liste *l* de carrés jusqu'à un million. \n",
    "- Créez un ensemble *s* de carrés jusqu'à un million. \n",
    "- Recherchez si $874466246641$ est un carré"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "033d6e9aecc254336000907e76e51bba",
     "grade": false,
     "grade_id": "cell-9786c9168deb0bf8",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "384b893ec029e5c4fd5e1237fea249ad",
     "grade": false,
     "grade_id": "cell-dab155c1b7e8021a",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Comparez les **temps de recherche d'un même nombre** dans l'ensemble et dans la liste. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "5f908ed0b3417afff41291ca3acb922f",
     "grade": true,
     "grade_id": "cell-ff81f5698da4dc52",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%time\n",
    "assert 874466246641 in s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ab0a3d7a67b4a3efbedb67b55e837d7c",
     "grade": true,
     "grade_id": "cell-904261d09bae96a6",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%time\n",
    "assert 874466246641 in l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "96a922fd224661eae3a5c56872911239",
     "grade": false,
     "grade_id": "cell-fdf2ccf339f5e160",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### quelques autres méthodes sur les set\n",
    "\n",
    "    s.isdisjoint(s2)\n",
    "    s.issubset(s2)\n",
    "    s.issuperset(s2)\n",
    "    s <= s2 : inclusion (pareil avec s >= s2).\n",
    "    s < s2 : inclusion stricte (pareil avec s >= s2).\n",
    "    set.union(s1, s2, s3) : renvoie la réunion de plusieurs sets.\n",
    "    set.intersection(s1, s2, s3) : renvoie l'intersection de plusieurs sets\n",
    "\n",
    "## Exercice\n",
    "\n",
    "Créer une fonction **ensembleCubes** prenant en paramètre un entier $n$ e renvoyant un ensemble contenant les cubes des entiers de 1 à $n$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "42cd896d6bb335e3723824d0f4421c6b",
     "grade": false,
     "grade_id": "cell-c640424ebd05c6d0",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def ensembleCubes(n):\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "931dad339cd33850ba5e42e5e452a3ca",
     "grade": true,
     "grade_id": "cell-e98ff42fb4d66d7b",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert 27 in ensembleCubes(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ef6b02470e9e9c05ab0f0b1ff51ee34c",
     "grade": false,
     "grade_id": "cell-bb8dba62282b3e4a",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "En déduire en une ligne de python combien de nombres entre 1 et 100 sont à la fois des carrés et des cubes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "986628205ecc42d5dca249426e861f84",
     "grade": true,
     "grade_id": "cell-369bb5f5aa7ee950",
     "locked": true,
     "points": 0,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Tapez votre ligne dans la cellule ci-dessous"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Attention, pas plus d'une ligne de Python !!"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Edit 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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}