{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Serie 10"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "from math import comb\n",
        "import random\n",
        "import matplotlib.pyplot as plt\n",
        "from numba import njit\n",
        "import time\n",
        "from tqdm.auto import tqdm"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NQcyc-p2_n1u"
      },
      "source": [
        "## Exercise 1"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GwgTJ5NB_oFs"
      },
      "source": [
        "#### Question 2"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "##### (a) Implémentez les deux approches **A** et **B**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "7ihfwsY9_j2q"
      },
      "outputs": [],
      "source": [
        "def is_valid_pair(x1: float, x2: float, sigma: float) -> bool:\n",
        "    return abs(x1 - x2) >= 2 * sigma\n",
        "\n",
        "def generate_configuration_A(N: int, L: float, sigma: float):\n",
        "    if L <= 2 * sigma * N:\n",
        "        raise ValueError(\"La condition L > 2σN n'est pas satisfaite. Veuillez choisir un L plus grand.\")\n",
        "    raise NotImplementedError\n",
        "\n",
        "\n",
        "def generate_configuration_B(N: int, L: float, sigma: float):\n",
        "    if L <= 2 * sigma * N:\n",
        "        raise ValueError(\"La condition L > 2σN n'est pas satisfaite. Veuillez choisir un L plus grand.\")\n",
        "    raise NotImplementedError\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "##### (b) Comparez les histogrammes obtenus pour $N=2$, $L=1$ et $\\sigma=0.1$ avec $n_{\\rm s} = 10^7$.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "xTgu0-DX_pUY",
        "outputId": "9cc95ca3-0ac5-4922-d2ab-b5b0f62733f2"
      },
      "outputs": [],
      "source": [
        "n_s = 10**7\n",
        "N = 2\n",
        "L = 1.0\n",
        "sigma = 0.1\n",
        "\n",
        "# Génération des configurations avec l'Approche A\n",
        "valid_positions_A = np.empty((n_s, N))\n",
        "for i in range(n_s):\n",
        "    valid_positions_A[i,:] = generate_configuration_A(N, L, sigma)\n",
        "\n",
        "# Génération des configurations avec l'Approche B\n",
        "valid_positions_B = np.empty((n_s, N))\n",
        "for i in range(n_s):\n",
        "    valid_positions_B[i,:] = generate_configuration_B(N, L, sigma)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "plt.figure(figsize=(12, 6))\n",
        "plt.subplot(1, 2, 1)\n",
        "plt.hist2d(valid_positions_A[:, 0], valid_positions_A[:, 1], bins=100, cmap='viridis', density=True)\n",
        "plt.xlabel('x1')\n",
        "plt.ylabel('x2')\n",
        "plt.title('Approach A')\n",
        "\n",
        "plt.subplot(1, 2, 2)\n",
        "\n",
        "plt.hist2d(valid_positions_B[:, 0], valid_positions_B[:, 1], bins=100, cmap='viridis', density=True)\n",
        "plt.xlabel('x1')\n",
        "plt.ylabel('x2')\n",
        "plt.title('Approach B')\n",
        "\n",
        "\n",
        "plt.suptitle(\"Histogramme 2D des positions\")\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "##### (c)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 564
        },
        "id": "zNNzv2nO_3_e",
        "outputId": "eaabb423-8c41-48bd-bfab-98c68022289b"
      },
      "outputs": [],
      "source": [
        "#question 3c\n",
        "plt.figure(figsize=(8, 6))\n",
        "plt.hist(valid_positions_B[:,0], bins=100, density=True, alpha=0.7, label='x1')\n",
        "plt.hist(valid_positions_B[:,1], bins=100, density=True, alpha=0.7, label='x2')\n",
        "plt.xlabel(\"Position\")\n",
        "plt.ylabel(\"Densité de probabilité\")\n",
        "plt.title(\"Distribution individuelle des positions (Approche B)\")\n",
        "plt.legend()\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Question 5"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "VRx1gIHRAwcS",
        "outputId": "e480df34-c0be-4ebc-adae-e19e8009c254"
      },
      "outputs": [],
      "source": [
        "# Fonction pour l'algorithme C : Tri des {yk}\n",
        "def algorithm_C(N: int, L: float, sigma: float) -> np.ndarray:\n",
        "    raise NotImplementedError"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "\n",
        "# Paramètres donnés\n",
        "L = 10\n",
        "sigma = 0.1\n",
        "N_values = range(1, 11)\n",
        "n_samples = 1000\n",
        "\n",
        "# Comparaison de l'efficacité des approches A, B et C\n",
        "average_attempts_A = []\n",
        "average_attempts_B = []\n",
        "average_attempts_C = []\n",
        "times_A = []\n",
        "times_B = []\n",
        "times_C = []\n",
        "\n",
        "for N in N_values:\n",
        "    # Mesure de l'efficacité de l'approche A\n",
        "    start_time_A = time.time()\n",
        "    attempts_A = []\n",
        "    for _ in range(n_samples):\n",
        "        attempts = 0\n",
        "        valid_positions = []\n",
        "        while len(valid_positions) < N:\n",
        "            attempts += 1\n",
        "            position = np.random.uniform(sigma, L - sigma)\n",
        "            if all(abs(position - vp) > 2 * sigma for vp in valid_positions):\n",
        "                valid_positions.append(position)\n",
        "        attempts_A.append(attempts)\n",
        "    end_time_A = time.time()\n",
        "    average_attempts_A.append(np.mean(attempts_A))\n",
        "    times_A.append(end_time_A - start_time_A)\n",
        "\n",
        "    # Mesure de l'efficacité de l'approche B\n",
        "    start_time_B = time.time()\n",
        "    attempts_B = []\n",
        "    for _ in range(n_samples):\n",
        "        attempts = 0\n",
        "        while True:\n",
        "            attempts += 1\n",
        "            valid_positions = []\n",
        "            for _ in range(N):\n",
        "                position = np.random.uniform(sigma, L - sigma)\n",
        "                if all(abs(position - vp) > 2 * sigma for vp in valid_positions):\n",
        "                    valid_positions.append(position)\n",
        "                else:\n",
        "                    break\n",
        "            if len(valid_positions) == N:\n",
        "                break\n",
        "        attempts_B.append(attempts)\n",
        "    end_time_B = time.time()\n",
        "    average_attempts_B.append(np.mean(attempts_B))\n",
        "    times_B.append(end_time_B - start_time_B)\n",
        "\n",
        "    # Mesure de l'efficacité de l'approche C\n",
        "    start_time_C = time.time()\n",
        "    attempts_C = []\n",
        "    for _ in range(n_samples):\n",
        "        attempts = 1  # L'algorithme C n'a besoin que d'une tentative car on trie les yk\n",
        "        algorithm_C(N, L, sigma)\n",
        "        attempts_C.append(attempts)\n",
        "    end_time_C = time.time()\n",
        "    average_attempts_C.append(np.mean(attempts_C))\n",
        "    times_C.append(end_time_C - start_time_C)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "\n",
        "# Tracé des courbes de comparaison\n",
        "plt.figure(figsize=(12, 12))\n",
        "\n",
        "# Nombre moyen d'essais pour chaque algorithme\n",
        "plt.subplot(2, 1, 1)\n",
        "plt.plot(N_values, average_attempts_A, 'r-o', label=\"Approche A : Nombre moyen d'essais\")\n",
        "plt.plot(N_values, average_attempts_B, 'g-^', label=\"Approche B : Nombre moyen d'essais\")\n",
        "plt.plot(N_values, average_attempts_C, 'b-s', label=\"Approche C : Nombre moyen d'essais\")\n",
        "plt.xlabel('N', fontsize=14)\n",
        "plt.ylabel('Nombre moyen d essais', fontsize=14)\n",
        "plt.title('Comparaison du nombre moyen d essais entre les approches A, B et C', fontsize=16)\n",
        "plt.legend(fontsize=12)\n",
        "plt.grid(True, linestyle='--', alpha=0.6)\n",
        "# plt.yscale('log')\n",
        "\n",
        "# Temps de calcul pour chaque algorithme\n",
        "plt.subplot(2, 1, 2)\n",
        "plt.plot(N_values, times_A, 'r-o', label=\"Approche A : Temps de calcul\")\n",
        "plt.plot(N_values, times_B, 'g-^', label=\"Approche B : Temps de calcul\")\n",
        "plt.plot(N_values, times_C, 'b-s', label=\"Approche C : Temps de calcul\")\n",
        "plt.xlabel('N', fontsize=14)\n",
        "plt.ylabel('Temps de calcul (secondes)', fontsize=14)\n",
        "plt.title('Comparaison du temps de calcul entre les approches A, B et C', fontsize=16)\n",
        "plt.legend(fontsize=12)\n",
        "plt.grid(True, linestyle='--', alpha=0.6)\n",
        "plt.yscale('log')\n",
        "\n",
        "plt.tight_layout()\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Question 7"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "##### (a)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 257
        },
        "id": "TsJa8RJ-_9ns",
        "outputId": "ee1c18cf-db1b-4e00-ea2e-d5c8098a10db"
      },
      "outputs": [],
      "source": [
        "# Paramètres\n",
        "L = 20\n",
        "sigma = 0.75\n",
        "N = 5  # Nombre de pinces\n",
        "\n",
        "# Génération de la configuration\n",
        "positions = []\n",
        "while len(positions) < N:\n",
        "    new_position = random.uniform(sigma, L - sigma)\n",
        "    valid = True\n",
        "    for pos in positions:\n",
        "        if abs(new_position - pos) < 2 * sigma:\n",
        "            valid = False\n",
        "            break\n",
        "    if valid:\n",
        "        positions.append(new_position)\n",
        "\n",
        "positions.sort()\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "\n",
        "# Visualisation de la situation\n",
        "plt.figure(figsize=(10, 2))\n",
        "plt.hlines(1, 0, L, colors='k', linestyles='-', linewidth=2)  # Corde à linge\n",
        "\n",
        "# Ajout des pinces\n",
        "for pos in positions:\n",
        "    plt.gca().add_patch(plt.Rectangle((pos - sigma, 0.9), 2 * sigma, 0.2, color='blue', alpha=0.6))\n",
        "\n",
        "plt.xlim(0, L)\n",
        "plt.ylim(0.8, 1.2)\n",
        "plt.xlabel(\"Position sur la corde à linge\")\n",
        "plt.title(\"Distribution des pinces sur une corde à linge de longueur L\")\n",
        "plt.gca().axes.yaxis.set_visible(False)\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "Mghc2jPOAQ-7",
        "outputId": "d8fa9655-389e-402a-cc7f-40472a4af765"
      },
      "outputs": [],
      "source": [
        "def Z_NLsigma(N,L,sigma):\n",
        "    raise NotImplementedError\n",
        "\n",
        "def pi_analytique(x, N, L, sigma):\n",
        "    raise NotImplementedError\n",
        "\n",
        "# Paramètres donnés\n",
        "L = 20\n",
        "sigma = 0.75\n",
        "N_values = [1, 5, 10]\n",
        "n_points = 10000  # Nombre de points pour l'évaluation de π_{L,N,σ}(x)\n",
        "x_vals = np.linspace(sigma, L - sigma, n_points)\n",
        "\n",
        "# Histogrammes simulés\n",
        "n_samples = 100000\n",
        "\n",
        "for N in N_values:\n",
        "    y_samples = []\n",
        "    for _ in range(n_samples):\n",
        "        # Algorithme C : Générer N variables y uniformément sur [0, L - 2Nσ] et les trier\n",
        "        yk = np.sort(np.random.uniform(0, L - 2 * N * sigma, N))\n",
        "        # Appliquer la transformation inverse\n",
        "        xk = yk + (2 * np.arange(1, N + 1) - 1) * sigma\n",
        "        y_samples.extend(xk)\n",
        "\n",
        "    # Création de l'histogramme\n",
        "    plt.hist(y_samples, bins=50, density=True, alpha=0.5, label=f'Simulation, N={N}')\n",
        "\n",
        "    # Calcul et tracé de la distribution analytique\n",
        "    pi_vals = [pi_analytique(x, N, L, sigma) for x in x_vals]\n",
        "    plt.plot(x_vals, pi_vals, label=f'Formule analytique, N={N}')\n",
        "\n",
        "    # Configuration du graphique\n",
        "    plt.xlabel('Position x')\n",
        "    plt.ylabel('Densité de probabilité')\n",
        "    plt.title(f'Comparaison de la distribution π_{{L,N,σ}}(x) pour N={N}')\n",
        "    plt.legend()\n",
        "    plt.show()\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "##### (b)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 885
        },
        "id": "0QglnAipAnHI",
        "outputId": "f8a50cba-b05f-4cf3-dd1d-3214af605bb0"
      },
      "outputs": [],
      "source": [
        "A_points = []\n",
        "B_points = []\n",
        "C_points = []\n",
        "A_list = []\n",
        "B_list = []\n",
        "C_list = []\n",
        "\n",
        "for N in range(1, 11):\n",
        "    pi_vals = [pi_analytique(x, N, L, sigma) for x in x_vals]\n",
        "    A_N = []\n",
        "    B_N = []\n",
        "    C_N = []\n",
        "    for i in range(1, len(pi_vals) - 1):\n",
        "        if pi_vals[i] < pi_vals[i - 1]-1e-16 and pi_vals[i] < pi_vals[i + 1]-1e-16:\n",
        "            A_N.append(x_vals[i])\n",
        "        if pi_vals[i] > pi_vals[i - 1]+1e-16 and pi_vals[i] > pi_vals[i + 1]+1e-16:\n",
        "            C_N.append(x_vals[i])\n",
        "        if  pi_vals[i]<1/L and  pi_vals[i+1]>=1/L or  pi_vals[i]>1/L and  pi_vals[i+1]<=1/L:\n",
        "            B_N.append(x_vals[i])\n",
        "    A_list.append(A_N)\n",
        "    B_list.append(B_N)\n",
        "    C_list.append(C_N)\n",
        "    A_points.append(len(A_N))\n",
        "    B_points.append(len(B_N))\n",
        "    C_points.append(len(C_N))\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "\n",
        "# Représentation graphique des ensembles A, B et C en fonction de N\n",
        "plt.figure(figsize=(12, 8))\n",
        "N_range = range(1, 11)\n",
        "plt.plot(N_range, A_points, 'r-', marker='o', linestyle='--', label='A : Local minima')\n",
        "plt.plot(N_range, B_points, 'g-', marker='s', linestyle='--', label='B : π(x) = 1/L')\n",
        "plt.plot(N_range, C_points, 'b-', marker='^', linestyle='--', label='C : Local maxima')\n",
        "\n",
        "plt.xlabel('N', fontsize=14)\n",
        "plt.ylabel('Set cardinality', fontsize=14)\n",
        "plt.title('Evolution of the cardinality of A, B, C as a function of N', fontsize=16)\n",
        "plt.xticks(fontsize=12)\n",
        "plt.yticks(fontsize=12)\n",
        "plt.legend(fontsize=12)\n",
        "plt.grid(True, linestyle='--', alpha=0.6)\n",
        "plt.show()\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "##### (c)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 746
        },
        "id": "JrKAqXUbDxy6",
        "outputId": "ffe619d2-8833-4783-abad-e4a8c477bf95"
      },
      "outputs": [],
      "source": [
        "plt.figure(figsize=(12, 8))\n",
        "colors = ['r', 'g', 'b']\n",
        "markers = ['o', 's', '^']\n",
        "labels = ['A : Local minima', 'B : π(x) = 1/L', 'C : Local maxima']\n",
        "\n",
        "for i, (points, color, marker, label) in enumerate(zip([A_list, B_list, C_list], colors, markers, labels)):\n",
        "    for N, x_vals_set in enumerate(points, start=1):\n",
        "        if isinstance(x_vals_set, list) and len(x_vals_set) > 0:\n",
        "            plt.scatter([N] * len(x_vals_set), x_vals_set, color=color, marker=marker, label=label if N == 5 else \"\", alpha=0.6)\n",
        "\n",
        "plt.xlabel('N', fontsize=14)\n",
        "plt.ylabel('Position x', fontsize=14)\n",
        "plt.title('Values of the points in A, B, C as a function of N', fontsize=16)\n",
        "plt.xticks(fontsize=12)\n",
        "plt.yticks(fontsize=12)\n",
        "plt.legend(fontsize=12, loc='best')\n",
        "plt.grid(True, linestyle='--', alpha=0.6)\n",
        "plt.show()\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "##### (d) Entropy!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": []
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "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.12.3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}