{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bijections, bijections, bijections ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Marc Lorenzi - Février 2018"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Une bijection de $\\mathbb N \\times \\mathbb N$ vers $\\mathbb N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 La fonction $\\varphi$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction $\\varphi:\\mathbb N \\to \\mathbb N$ définie par $\\varphi(n)=\\frac 1 2 n(n+1)$ est une injection strictement croissante."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def phi(n):\n",
    "    return n * (n + 1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[(k, phi(k)) for k in range(11)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comme $\\varphi(0) = 0$ et $\\varphi$ est strictement croissante, pour tout entier naturel $t$ il existe un unique entier $n$ tel que $\\varphi(n)\\le t <\\varphi(n+1)$. Cet entier $n$ peut être obtenu par dichotomie."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_phi(t):\n",
    "    a = 0\n",
    "    b = t + 1\n",
    "    while b - a > 1:\n",
    "        c = (a + b) // 2\n",
    "        if phi(c) <= t: a = c\n",
    "        else: b = c\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_phi(123456789)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "phi(15712), phi(15713)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 La fonction $f_2$ et sa réciproque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction $f_2:\\mathbb N\\times\\mathbb N$ définie par $f_2(x,y) = \\varphi(x+y) + y$ est une bijection."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f2(x, y):\n",
    "    n = x + y\n",
    "    return phi(n) + y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $t\\in\\mathbb N$. Soit $n$ tel que $\\varphi(n)\\le t < \\varphi(n+1)$. Posons alors $y=t-\\varphi(n)$ et $x=n-y$. On vérifie facilement que $x,y\\in\\mathbb N$ et $f_2(x,y)=t$. Il est donc aisé de coder la réciproque de la fonction $f_2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recip_f2(t):\n",
    "    n = max_phi(t)\n",
    "    y = t - phi(n)\n",
    "    x = n - y\n",
    "    return (x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "recip_f2(123456789)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f2(251, 15461)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "recip_f2(10 ** 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "recip_f2(10 ** 100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Tests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un million de tests pour se convaincre que `f2` et `recip_f2` sont bien réciproques l'une de l'autre ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for t in range(10 ** 6 + 1):\n",
    "    (x, y) = recip_f2(t)\n",
    "    assert f2(x, y) == t\n",
    "print('test 1 ok')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in range(1001):\n",
    "    for y in range(1001):\n",
    "        assert recip_f2(f2(x, y)) == (x, y)\n",
    "print('test 2 ok')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Une bijection de $\\mathbb N^3$ vers $\\mathbb N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ayant écrit une bijection de $\\mathbb N^2$ vers $\\mathbb N$, il est simple d'écrire une bijection de $\\mathbb N^3$ vers $\\mathbb N$, en remarquant que $\\mathbb N^3$ est en bijection avec $\\mathbb N\\times\\mathbb N^2$. Cela nous donne la fonction $f_3:\\mathbb N^3\\to\\mathbb N$ définie par $f_3(x, y, z)=f_2(x,f_2(y, z))$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f3(x, y, z):\n",
    "    return f2(x, f2(y, z))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La réciproque de $f_3$ est facile à obtenir puisqu'on connaît celle de $f_2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recip_f3(t):\n",
    "    (x, u) = recip_f2(t)\n",
    "    (y, z) = recip_f2(u)\n",
    "    return (x, y, z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f3(123, 456, 789)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "recip_f3(10 ** 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f3(6280, 62, 214)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Une bijection de $\\mathbb L^*$ vers $\\mathbb N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notons $\\mathbb L$ l'ensemble des listes d'entiers, et $\\mathbb L^*$ l'ensemble des listes non vides d'entiers. La fonction $g$ ci-dessous prend en paramètre une liste $s$ non vide, s'appelle récursivement sur les deux moitiés de $s$ pour calculer deux entiers, et applique la fonction $f_2$ à ces deux entiers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def g(s):\n",
    "    if len(s) == 1: return s[0]\n",
    "    else:\n",
    "        p = len(s)\n",
    "        q = p // 2\n",
    "        s1 = s[0:q]\n",
    "        s2 = s[q:]\n",
    "        return f2(g(s1), g(s2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g(range(1, 11))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si l'on connaît la longueur de la liste $s$ passée en paramètre à $g$, on peut alors retrouver $s$ à partir de $g(s)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recip_g(p, t):\n",
    "    if p == 1: return [t]\n",
    "    else:\n",
    "        U, V = recip_f2(t)\n",
    "        p1 = p // 2\n",
    "        p2 = p - p1\n",
    "        Y = recip_g(p1, U)\n",
    "        Z = recip_g(p2, V)\n",
    "        return Y + Z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = recip_g(10, 10 ** 40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour parfaire le tout, en composant $g$ et $f_2$, on peut englober l'information sur la longueur de $s$ dans l'entier renvoyé par la fonction. La fonction $f$ ci-dessous est ainsi une bijection de $\\mathbb L^*$ vers $\\mathbb N$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(s):\n",
    "    p = len(s)\n",
    "    return f2(g(s), p - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f([1, 5, 2, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recip_f(t):\n",
    "    y, p = recip_f2(t)\n",
    "    return recip_g(p + 1, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "recip_f(511569)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Une bijection de $\\mathbb L$ vers $\\mathbb N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un petit décalage permet enfin de créer une bijection $F:\\mathbb L\\to\\mathbb N$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(s):\n",
    "    if len(s) == 0: return 0\n",
    "    else: return f(s) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = F(range(11))\n",
    "t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recip_F(t):\n",
    "    if t == 0: return []\n",
    "    else: return recip_f(t - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "recip_F(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Faisons quelques tests ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_list(n):\n",
    "    return [random.randint(0, 1000) for k in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_list(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test(n):\n",
    "    s = random_list(n)\n",
    "    print('s = ', s)\n",
    "    t = F(s)\n",
    "    print('F(s) = ', t)\n",
    "    s1 = recip_F(t)\n",
    "    print('recip_F(t) = ', s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test(15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}