Combinatoire et dénombrement.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Combinatoire et dénombrement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Pour un entier $n$ donné, génération de la liste des coefficients $\\binom{n}{k}$ à l'aide de la relation de Pascal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Rappel :**\n",
    "\n",
    "La formule de Pascal est la suivante :\n",
    "\n",
    "Soit un entier naturel $n$ supérieur ou égal à 2 et $k$ un entier naturel tel que $1\\leq k\\leq n-1$.\n",
    "\n",
    "Alors $\\binom{n}{k}=\\binom{n-1}{k-1}+\\binom{n-1}{k}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Remarque :**\n",
    "\n",
    "Le programme qui suit va faire appel à un principe algorithme qui peut perturber certains élèves : la récursivité.\n",
    "\n",
    "À l'intérieur du code, on retrouve un appel au code lui-même !...mais avec des valeurs plus faibles.\n",
    "\n",
    "Pour qu'un tel programme donne bien la bonne solution, il est donc nécessaire d'avoir dans le code :\n",
    "\n",
    "1. une relation type récurrence permettant à partir de valeurs inférieures des arguments d'obtenir ce que l'on cherche\n",
    "\n",
    "2. la valeur pour les cas les plus simples qui sont nécessaires pour initialiser le raisonnement\n",
    "\n",
    "Cela ressemble énormément à un raisonnement par récurrence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "10\n",
      "45\n",
      "120\n",
      "210\n",
      "252\n",
      "210\n",
      "120\n",
      "45\n",
      "10\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "def binom(n, k):\n",
    "    \"\"\"Cette fonction prend en arguments deux entiers n et k vérifiant\n",
    "    0<=k<=n et renvoie le coefficient binomial k parmi n\"\"\"\n",
    "    # test de la condition sur k et n\n",
    "    assert 0<= k <= n\n",
    "    # cas de base\n",
    "    if k == 0 or k == n:\n",
    "        return 1\n",
    "    else :\n",
    "        return binom(n-1, k-1) + binom(n-1 ,k)\n",
    "\n",
    "for k in range(11):\n",
    "    print(binom(10, k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Remarque :**\n",
    "\n",
    "Les lignes comprises entre `\"\"\"...\"\"\"` suivant le nom de la fonction forme ce qu'on appelle une *docstring*.\n",
    "\n",
    "Elle sert à donner des informations sur la fonction et on peut visualiser ces informations en tapant `help(nom_fonction)` (soit ici `help(binom)`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Génération d'une liste**\n",
    "\n",
    "Avec des entiers $n$ et $k$ (tels que $0\\leq k\\leq n$), génération de la liste des coefficients binomiaux $\\binom{n}{k}$ pour $k$ compris entre 0 et $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 10, 10, 5, 1]\n"
     ]
    }
   ],
   "source": [
    "def liste_binom(n):\n",
    "    return [binom(n, k) for k in range(n+1)]\n",
    "\n",
    "print(liste_binom(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Génération du triangle de Pascal jusqu'à une ligne $n$ données**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vous allez obtenir le triangle de Pascal jusqu'à la ligne n.\n",
      "Quel est votre choix pour n ?\n",
      "10\n",
      "[1]\n",
      "[1, 1]\n",
      "[1, 2, 1]\n",
      "[1, 3, 3, 1]\n",
      "[1, 4, 6, 4, 1]\n",
      "[1, 5, 10, 10, 5, 1]\n",
      "[1, 6, 15, 20, 15, 6, 1]\n",
      "[1, 7, 21, 35, 35, 21, 7, 1]\n",
      "[1, 8, 28, 56, 70, 56, 28, 8, 1]\n",
      "[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]\n",
      "[1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]\n"
     ]
    }
   ],
   "source": [
    "# Demande de l'entier n à l'utilisateur\n",
    "n = int(input(\"\"\"Vous allez obtenir le triangle de Pascal jusqu'à la ligne n.\n",
    "Quel est votre choix pour n ?\\n\"\"\"))\n",
    "\n",
    "for m in range(n+1):\n",
    "    print(liste_binom(m))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Génération des permutations d'un ensemble fini"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Version *non récursive* dans le cas où l'ensemble possède trois éléments :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['aa', 'bb', 'cc'],\n",
       " ['aa', 'cc', 'bb'],\n",
       " ['bb', 'aa', 'cc'],\n",
       " ['bb', 'cc', 'aa'],\n",
       " ['cc', 'aa', 'bb'],\n",
       " ['cc', 'bb', 'aa']]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def liste_permutations3(L):\n",
    "    \"\"\"Cette fonction prend comme argument une liste contenant 3 éléments et\n",
    "    renvoie la liste de toutes les permutations de L\"\"\"\n",
    "    assert len(L) == 3 # vérification de la longueur de la liste\n",
    "    permutations = [] # liste des permutations initialisée vide\n",
    "    for i in range(3):\n",
    "        L_i_1 = [L[i]]\n",
    "        L_i_2 = [L[i]]\n",
    "        L_i = L.copy()\n",
    "        L_i.pop(i)\n",
    "        L_i_1.append(L_i[0])\n",
    "        L_i_1.append(L_i[1])\n",
    "        L_i_2.append(L_i[1])\n",
    "        L_i_2.append(L_i[0])\n",
    "        permutations.append(L_i_1)\n",
    "        permutations.append(L_i_2)\n",
    "    return permutations\n",
    "\n",
    "L = [\"aa\", \"bb\", \"cc\"]\n",
    "liste_permutations3(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une version *récursive* dans le cas général :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]\n"
     ]
    }
   ],
   "source": [
    "def liste_permutations2(L):\n",
    "    \"\"\"Cette fonction prend comme argument une liste d'éléments et\n",
    "    renvoie la liste de toutes les permutations de L\"\"\"\n",
    "    n = len(L)\n",
    "    if n == 1:\n",
    "        return [L]\n",
    "    else :\n",
    "        permutations = []\n",
    "        for k in range(n):\n",
    "            M = L.copy() # copie de la liste L\n",
    "            # pour pouvoir supprimer l'élément de rang k sans modifier L\n",
    "            M.pop(k)\n",
    "            permutations += [[L[k]]+liste for liste in liste_permutations2(M)]\n",
    "        return permutations\n",
    "\n",
    "L = list(range(1, 5)) # Liste des entiers de 1 à 4\n",
    "print(liste_permutations2(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Tirage aléatoire d'une permutation d'une liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['cc', 'aa', 'bb']\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "def permutation(L):\n",
    "    \"\"\"Cette fonction prend en argument une liste et\n",
    "    renvoie une permutation aléatoire de cette liste\"\"\"\n",
    "    random.shuffle(L) # permet de mélanger la liste\n",
    "    return L\n",
    "\n",
    "L = [\"aa\", \"bb\", \"cc\"]\n",
    "print(permutation(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Génération des parties à 2, 3 éléments d'un ensemble fini"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3], [0, 4], [1, 4], [2, 4], [3, 4]]\n"
     ]
    }
   ],
   "source": [
    "def liste_parties2(L):\n",
    "    \"\"\"Cette fonction prend en arguments une liste L et \n",
    "    renvoie toutes les parties de L à 2 éléments,\n",
    "    chaque partie étant écrite sous forme d'une liste\"\"\"\n",
    "    parties = []\n",
    "    n = len(L)\n",
    "    for k in range(n):\n",
    "        for i in range(k):\n",
    "            Liste = [L[i], L[k]]\n",
    "            parties.append(Liste)\n",
    "    return parties\n",
    "\n",
    "L = list(range(5))\n",
    "print(liste_parties2(L))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3], [0, 4], [1, 4], [2, 4], [3, 4]]\n"
     ]
    }
   ],
   "source": [
    "# Autre version\n",
    "def parties_deux_elts(L):\n",
    "    \"\"\"Cette fonction prend en arguments une liste L et \n",
    "    renvoie toutes les parties de L à 2 éléments,\n",
    "    chaque partie étant écrite sous forme d'une liste\"\"\"\n",
    "    n = len(L)\n",
    "    return [[L[i], L[j]] for j in range(n) for i in range(j)]\n",
    "\n",
    "L = list(range(5))\n",
    "print(parties_deux_elts(L))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3], [0, 1, 4], [0, 2, 4], [1, 2, 4], [0, 3, 4], [1, 3, 4], [2, 3, 4]]\n"
     ]
    }
   ],
   "source": [
    "def liste_parties3(L):\n",
    "    \"\"\"Cette fonction prend en arguments une liste L et \n",
    "    renvoie toutes les parties de L à 3 éléments,\n",
    "    chaque partie étant écrite sous forme d'une liste\"\"\"\n",
    "    parties = []\n",
    "    n = len(L)\n",
    "    for k in range(n):\n",
    "        for j in range(k):\n",
    "            for i in range(j):\n",
    "                Liste = [L[i], L[j], L[k]]\n",
    "                parties.append(Liste)\n",
    "    return parties\n",
    "\n",
    "L = list(range(5))\n",
    "print(liste_parties3(L))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3], [0, 1, 4], [0, 2, 4], [1, 2, 4], [0, 3, 4], [1, 3, 4], [2, 3, 4]]\n"
     ]
    }
   ],
   "source": [
    "# Autre version\n",
    "def parties_trois_elts(L):\n",
    "    \"\"\"Cette fonction prend en arguments une liste L et \n",
    "    renvoie toutes les parties de L à 3 éléments,\n",
    "    chaque partie étant écrite sous forme d'une liste\"\"\"\n",
    "    n = len(L)\n",
    "    return [[L[i], L[j], L[k]] for k in range(n) for j in range(k) for i in range(j)]\n",
    "\n",
    "L = list(range(5))\n",
    "print(parties_trois_elts(L))"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}