euromillions_jackpot.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "jackpot-complexidade-de-algoritmos.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "bFCyibLXjL7b",
        "IvftVCqyy1h2",
        "CBz3hb6Tl1uY",
        "xWqiU2-2t74F"
      ]
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 87,
      "metadata": {
        "id": "yRdwiff19Mq3"
      },
      "outputs": [],
      "source": [
        "from itertools import chain, combinations\n",
        "import math\n",
        "import numpy as np\n",
        "import pandas as pd\n",
        "import random\n",
        "from ast import literal_eval\n",
        "import matplotlib.pyplot as plt"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **SOMATIVA 01**: Complexidade de Algoritmos\n",
        "Dados 50 números inteiros de 1 a 50 e as seguintes combinações, escreva os **programas** pedidos nos itens abaixo.\n",
        "\n",
        "$$ {{n=50}\\choose{p=5}} = 2.118.760 $$\n",
        "\n",
        "$$ {{n=50}\\choose{p=4}} = 230.300 $$\n",
        "\n",
        "$$ {{n=50}\\choose{p=3}} = 19.600 $$\n",
        "\n",
        "$$ {{n=50}\\choose{p=2}} = 1.225 $$"
      ],
      "metadata": {
        "id": "M0lIY6Cvailt"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **CALCULANDO** $C_{n,p}$\n",
        "\n",
        "O número de combinações ${{n}\\choose{p}}$ é dado por\n",
        "\n",
        "$$ \\binom np=C_{n,p}=\\frac{n!}{p!(n-p)!} $$\n",
        "\n",
        "Abaixo, estão calculados os valores de combinações listados acima, utilizando a fórmula apresentada"
      ],
      "metadata": {
        "id": "bFCyibLXjL7b"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# função que calcula o número de combinações\n",
        "def combinations_count(n, r):\n",
        "    f = math.factorial\n",
        "    return f(n) / (f(r) * f(n-r))\n",
        "\n",
        "# número de combinações\n",
        "print('(a)', int(combinations_count(50, 5))) # (a)\n",
        "print('(b)', int(combinations_count(50, 4))) # (b)\n",
        "print('(c)', int(combinations_count(50, 3))) # (c)\n",
        "print('(d)', int(combinations_count(50, 2))) # (d)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "yYd-Cc6hHLEc",
        "outputId": "b1c80d7d-9330-4928-8e78-882aff369309"
      },
      "execution_count": 283,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(a) 2118760\n",
            "(b) 230300\n",
            "(c) 19600\n",
            "(d) 1225\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "math.factorial(5) / (math.factorial(2) * math.factorial(3)) # 1\n",
        "# 10/10 = 1"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zc63j2hbE5Zk",
        "outputId": "7b5ab7e8-c697-4140-b78a-295b1c5e8384"
      },
      "execution_count": 290,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "10.0"
            ]
          },
          "metadata": {},
          "execution_count": 290
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "math.factorial(6) / (math.factorial(2) * math.factorial(4)) # 3\n",
        "# 15/5 = 3"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "cBwf3xWdEA34",
        "outputId": "ccca7c97-0648-49b0-c016-bf6be962d884"
      },
      "execution_count": 288,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "15.0"
            ]
          },
          "metadata": {},
          "execution_count": 288
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "n = 7\n",
        "p = 2\n",
        "math.factorial(n) / (math.factorial(p) * math.factorial(n-p)) # 3\n",
        "# 21/7 = 3"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pGy-9igWE3-g",
        "outputId": "49042b93-6732-4701-a822-cfca860adf67"
      },
      "execution_count": 291,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "21.0"
            ]
          },
          "metadata": {},
          "execution_count": 291
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "n = 8\n",
        "p = 2\n",
        "math.factorial(n) / (math.factorial(p) * math.factorial(n-p)) # 4\n",
        "# 28/7 = 4"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zfRbDytYFRyP",
        "outputId": "57b4dc2f-d032-4690-ca56-3fc687856058"
      },
      "execution_count": 293,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "28.0"
            ]
          },
          "metadata": {},
          "execution_count": 293
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "n = 9\n",
        "p = 2\n",
        "math.factorial(n) / (math.factorial(p) * math.factorial(n-p)) # 5\n",
        "# 36/ = 5"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "gjtcLebbFZGJ",
        "outputId": "6c2ef37c-7f78-4805-d591-9a88eeb7bf1b"
      },
      "execution_count": 294,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "36.0"
            ]
          },
          "metadata": {},
          "execution_count": 294
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **ITEM 01**) Gerando as combinações de ($a$), ($b$), ($c$) e ($d$) (**PROGRAMA 01**)"
      ],
      "metadata": {
        "id": "GHFks0ROamJk"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Algoritmos de combinação"
      ],
      "metadata": {
        "id": "IvftVCqyy1h2"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# (1,2) (2,3) (3,4) (4,5) (5,6)\n",
        "# (1,3) (2,4) (3,5) (4,6)\n",
        "# (1,4) (2,5) (3,6)\n",
        "# (1,5) (2,6)\n",
        "# (1,6) \n",
        "\n",
        "def combinations_p2(array, show=False):\n",
        "    for i, column_comb in enumerate(array):\n",
        "        if show: print(i, column_comb)\n",
        "        for k in range(i+1, len(array)):\n",
        "            if show: print((column_comb, array[k]))\n",
        "            yield (column_comb, array[k])\n",
        "        if show: print()\n",
        "\n",
        "combs = list(combinations_p2(range(1,6+1), show=True))\n",
        "print('len =', len(combs))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "15Xd4pSrUqHd",
        "outputId": "d39857da-c620-4a53-bd2c-f2c15215656c"
      },
      "execution_count": 107,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0 1\n",
            "(1, 2)\n",
            "(1, 3)\n",
            "(1, 4)\n",
            "(1, 5)\n",
            "(1, 6)\n",
            "\n",
            "1 2\n",
            "(2, 3)\n",
            "(2, 4)\n",
            "(2, 5)\n",
            "(2, 6)\n",
            "\n",
            "2 3\n",
            "(3, 4)\n",
            "(3, 5)\n",
            "(3, 6)\n",
            "\n",
            "3 4\n",
            "(4, 5)\n",
            "(4, 6)\n",
            "\n",
            "4 5\n",
            "(5, 6)\n",
            "\n",
            "5 6\n",
            "\n",
            "len = 15\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "array = range(1,6+1)\n",
        "permutations = []\n",
        "for i in range(1,len(array)+1):\n",
        "    for j in range(1,len(array)+1):\n",
        "        permutations.append((i,j))\n",
        "\n",
        "combs = list(set([e for e in [tuple(k) for k in [set(i) for i in permutations]] if len(e) > 1]))\n",
        "\n",
        "print('len =', len(combs))\n",
        "print('len by itertools =', len(list(combinations(range(1,6+1), 2))))\n",
        "\n",
        "combs = sorted([tuple(sorted(t)) for t in combs])\n",
        "combs"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hpOvflAfgJdw",
        "outputId": "83fcb591-1dea-47e7-f350-097a7d7efced"
      },
      "execution_count": 217,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "len = 15\n",
            "len by itertools = 15\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(1, 2),\n",
              " (1, 3),\n",
              " (1, 4),\n",
              " (1, 5),\n",
              " (1, 6),\n",
              " (2, 3),\n",
              " (2, 4),\n",
              " (2, 5),\n",
              " (2, 6),\n",
              " (3, 4),\n",
              " (3, 5),\n",
              " (3, 6),\n",
              " (4, 5),\n",
              " (4, 6),\n",
              " (5, 6)]"
            ]
          },
          "metadata": {},
          "execution_count": 217
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "array = range(1,6+1)\n",
        "permutations = []\n",
        "for i in range(1,len(array)+1):\n",
        "    for j in range(1,len(array)+1):\n",
        "        for k in range(1,len(array)+1):\n",
        "            permutations.append((i,j,k))\n",
        "\n",
        "combs = list(set([e for e in [tuple(k) for k in [set(i) for i in permutations]] if len(e) > 2]))\n",
        "\n",
        "print('len =', len(combs))\n",
        "print('len by itertools =', len(list(combinations(range(1,6+1), 3))))\n",
        "\n",
        "combs = sorted([tuple(sorted(t)) for t in combs])\n",
        "combs"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ghof9PIVhGMd",
        "outputId": "c3b206fd-4c07-4800-fc26-93cdbce014b2"
      },
      "execution_count": 216,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "len = 20\n",
            "len by itertools = 20\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(1, 2, 3),\n",
              " (1, 2, 4),\n",
              " (1, 2, 5),\n",
              " (1, 2, 6),\n",
              " (1, 3, 4),\n",
              " (1, 3, 5),\n",
              " (1, 3, 6),\n",
              " (1, 4, 5),\n",
              " (1, 4, 6),\n",
              " (1, 5, 6),\n",
              " (2, 3, 4),\n",
              " (2, 3, 5),\n",
              " (2, 3, 6),\n",
              " (2, 4, 5),\n",
              " (2, 4, 6),\n",
              " (2, 5, 6),\n",
              " (3, 4, 5),\n",
              " (3, 4, 6),\n",
              " (3, 5, 6),\n",
              " (4, 5, 6)]"
            ]
          },
          "metadata": {},
          "execution_count": 216
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "array = range(1,6+1)\n",
        "permutations = []\n",
        "for i in range(1,len(array)+1):\n",
        "    for j in range(1,len(array)+1):\n",
        "        for k in range(1,len(array)+1):\n",
        "            for l in range(1,len(array)+1):\n",
        "                permutations.append((i,j,k,l))\n",
        "\n",
        "combs = list(set([e for e in [tuple(k) for k in [set(i) for i in permutations]] if len(e) > 3]))\n",
        "\n",
        "print('len =', len(combs))\n",
        "print('len by itertools =', len(list(combinations(range(1,6+1), 4))))\n",
        "\n",
        "combs = sorted([tuple(sorted(t)) for t in combs])\n",
        "combs"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "752bc005-aa9e-4ca9-aae4-5a6b202594ff",
        "id": "k-uY27JnmdvK"
      },
      "execution_count": 209,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "len = 15\n",
            "len by itertools = 15\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(1, 2, 3, 4),\n",
              " (1, 2, 3, 5),\n",
              " (1, 2, 3, 6),\n",
              " (1, 2, 4, 5),\n",
              " (1, 2, 4, 6),\n",
              " (1, 2, 5, 6),\n",
              " (1, 3, 4, 5),\n",
              " (1, 3, 4, 6),\n",
              " (1, 3, 5, 6),\n",
              " (1, 4, 5, 6),\n",
              " (2, 3, 4, 5),\n",
              " (2, 3, 4, 6),\n",
              " (2, 3, 5, 6),\n",
              " (2, 4, 5, 6),\n",
              " (3, 4, 5, 6)]"
            ]
          },
          "metadata": {},
          "execution_count": 209
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def n_combinations(iterable, r):\n",
        "    char = tuple(iterable)\n",
        "    n = len(char)\n",
        "    if r > n:\n",
        "        return\n",
        "    index = np.arange(r)\n",
        "    yield tuple(char[i] for i in index)\n",
        "    while True:\n",
        "        for i in reversed(range(r)):\n",
        "            if index[i] != i + n - r:\n",
        "                break\n",
        "        else:\n",
        "            return\n",
        "        index[i] += 1\n",
        "        for j in range(i + 1, r):\n",
        "            index[j] = index[j-1] + 1\n",
        "        yield tuple(char[i] for i in index)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TRO1JCSH4u2S",
        "outputId": "517ffd92-8c97-41da-9004-8221413e99f7"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1225"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "c2 = [x for x in n_combinations(range(1,50+1), 2)]\n",
        "print(len(c2))\n",
        "\n",
        "c5 = [x for x in n_combinations(range(1,50+1), 5)]\n",
        "print(len(c5))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "OPG9SzVS5TLD",
        "outputId": "8ca8d178-2f6e-441a-e53c-5a10abb8323f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2118760"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Combinações utilizando `for`"
      ],
      "metadata": {
        "id": "MX0VGI-tyiNu"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "array = list(range(1,50+1))\n",
        "n = len(array)"
      ],
      "metadata": {
        "id": "qz75pgwc0Ata"
      },
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# combinações 2 a 2 de 1 a 50\n",
        "cobinations_p2 = []\n",
        "for i in range(0, n-1):\n",
        "    for j in range(i+1, n):\n",
        "        cobinations_p2.append([array[i], array[j]])\n",
        "\n",
        "print(len(cobinations_p2))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "SS5M5rJCzSo4",
        "outputId": "ea2212a4-6370-40f3-ab70-987a14c966b3"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1225\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# combinações 3 a 3 de 1 a 50\n",
        "combinations_p3 = []\n",
        "for i in range(0, n-2):\n",
        "    for j in range(i+1, n-1):\n",
        "        for k in range(j+1, n):\n",
        "            combinations_p3.append([array[i], array[j], array[k]])\n",
        "\n",
        "print(len(combinations_p3))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9BcAjZwVy6en",
        "outputId": "245bda13-9a6f-4a8d-f994-27fe8a83605c"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "19600\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# combinações 4 a 4 de 1 a 50\n",
        "combinations_p4 = []\n",
        "for i in range(0, n-3):\n",
        "    for j in range(i+1, n-2):\n",
        "        for k in range(j+1, n-1):\n",
        "            for m in range(k+1, n):\n",
        "                combinations_p4.append((array[i], \n",
        "                                        array[j],\n",
        "                                        array[k],\n",
        "                                        array[m]))\n",
        "\n",
        "print(len(combinations_p4))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rAKC_v80wRjt",
        "outputId": "a1583afa-9f10-4698-9e9f-ef00f59c91bf"
      },
      "execution_count": 38,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "230300\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# combinações 5 a 5 de 1 a 50\n",
        "combinations_p5 = []\n",
        "for i in range(0, n-4):\n",
        "    for j in range(i+1, n-3):\n",
        "        for k in range(j+1, n-2):\n",
        "            for m in range(k+1, n-1):\n",
        "                for o in range(m+1, n):\n",
        "                    combinations_p5.append((array[i], \n",
        "                                            array[j], \n",
        "                                            array[k], \n",
        "                                            array[m], \n",
        "                                            array[o]))\n",
        "len(combinations_p5)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RHeX8Ri1xx0w",
        "outputId": "f2956be1-9f74-41d4-bafa-08f1df5afcc9"
      },
      "execution_count": 37,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2118760"
            ]
          },
          "metadata": {},
          "execution_count": 37
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Gerando através da biblioteca `itertools`"
      ],
      "metadata": {
        "id": "CBz3hb6Tl1uY"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "n = range(1, 51)\n",
        "\n",
        "c5 = list(combinations(n, 5)) # (a)\n",
        "c4 = list(combinations(n, 4)) # (b)\n",
        "c3 = list(combinations(n, 3)) # (c)\n",
        "c2 = list(combinations(n, 2)) # (d)\n",
        "\n",
        "# tamanho dos arrays de combinações\n",
        "print('(a)', len(c5)) # (a)\n",
        "print('(b)', len(c4)) # (b)\n",
        "print('(c)', len(c3)) # (c)\n",
        "print('(d)', len(c2)) # (d)"
      ],
      "metadata": {
        "id": "7-XH_NqUInFa",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "16b48c87-14d4-4e5a-cf0e-d0271411436c"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(a) 2118760\n",
            "(b) 230300\n",
            "(c) 19600\n",
            "(d) 1225\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Entendendo o problema"
      ],
      "metadata": {
        "id": "Xr-v4JVc0XiE"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "c5 = list(combinations(range(1,7+1), 5))\n",
        "\n",
        "# [(1, 2, 3, 5, 6), (1, 2, 4, 5, 7), (3, 4, 5, 6, 7)]\n",
        "for i in c5:\n",
        "    print(i)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "03Q1U8h-3UPZ",
        "outputId": "010d5f39-ae87-4a8d-96cc-40d3ea907d52"
      },
      "execution_count": 275,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(1, 2, 3, 4, 5)\n",
            "(1, 2, 3, 4, 6)\n",
            "(1, 2, 3, 4, 7)\n",
            "(1, 2, 3, 5, 6)\n",
            "(1, 2, 3, 5, 7)\n",
            "(1, 2, 3, 6, 7)\n",
            "(1, 2, 4, 5, 6)\n",
            "(1, 2, 4, 5, 7)\n",
            "(1, 2, 4, 6, 7)\n",
            "(1, 2, 5, 6, 7)\n",
            "(1, 3, 4, 5, 6)\n",
            "(1, 3, 4, 5, 7)\n",
            "(1, 3, 4, 6, 7)\n",
            "(1, 3, 5, 6, 7)\n",
            "(1, 4, 5, 6, 7)\n",
            "(2, 3, 4, 5, 6)\n",
            "(2, 3, 4, 5, 7)\n",
            "(2, 3, 4, 6, 7)\n",
            "(2, 3, 5, 6, 7)\n",
            "(2, 4, 5, 6, 7)\n",
            "(3, 4, 5, 6, 7)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# powerset para 6 elementos\n",
        "c2 = list(combinations(range(1,6+1), 2))\n",
        "c5 = list(combinations(range(1,6+1), 5))\n",
        "\n",
        "print('len c2 =', len(c2))\n",
        "print('len c5 =', len(c5), end='\\n\\n')\n",
        "\n",
        "print('c2 =', c2)\n",
        "print('c5 =', c5, end='\\n\\n')\n",
        "\n",
        "c5_all = []\n",
        "a = list(combinations(c5, 6))\n",
        "b = list(combinations(c5, 5))\n",
        "c = list(combinations(c5, 4))\n",
        "d = list(combinations(c5, 3))\n",
        "e = list(combinations(c5, 2))\n",
        "f = list(combinations(c5, 1))\n",
        "\n",
        "l = [a, b, c, d, e, f]\n",
        "\n",
        "for i in l:\n",
        "    c5_all.extend(i)\n",
        "\n",
        "# (1,2,3,4,5) (1,2,4,5,6) (1,3,4,5,6)\n",
        "\n",
        "# powerset para 6 elementos\n",
        "print(f'2**len(c5) = 2**{len(c5)} =', 2**(len(c5)))\n",
        "print('len powerset =', len(c5_all))\n",
        "for i in c5_all:\n",
        "    print(i)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GtPVp04gw8ix",
        "outputId": "094052d9-03b5-49dc-8bd1-d613b0ea8c51"
      },
      "execution_count": 232,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "len c2 = 15\n",
            "len c5 = 6\n",
            "\n",
            "c2 = [(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]\n",
            "c5 = [(1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6)]\n",
            "\n",
            "2**len(c5) = 2**6 = 64\n",
            "len powerset = 63\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 4, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 3, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 2, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 3, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 2, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 5, 6), (1, 2, 4, 5, 6))\n",
            "((1, 2, 3, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 3, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 4, 5, 6), (1, 3, 4, 5, 6))\n",
            "((1, 2, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 3, 4, 5, 6), (2, 3, 4, 5, 6))\n",
            "((1, 2, 3, 4, 5),)\n",
            "((1, 2, 3, 4, 6),)\n",
            "((1, 2, 3, 5, 6),)\n",
            "((1, 2, 4, 5, 6),)\n",
            "((1, 3, 4, 5, 6),)\n",
            "((2, 3, 4, 5, 6),)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "n = len(list(combinations(range(1,9+1), 2)))\n",
        "print(n)\n",
        "2**n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Oboh_uCPzZBD",
        "outputId": "14afbbd0-4ea8-4d3f-c504-ac965cbc0924"
      },
      "execution_count": 242,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "36\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "68719476736"
            ]
          },
          "metadata": {},
          "execution_count": 242
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **ALGORITMO**: `minor_elements_set` que gera os conjuntos $S_i$"
      ],
      "metadata": {
        "id": "5CRWOxdaXZnb"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Algoritmo a ser usado nos programas 02, 03 e 04, tentando gerar o menor conjunto que contém combinações de 5 elementos, estas que por sua vez contém todas as demais combinações de, respectivamente, 2, 3 e 4 elementos ($S_1$, $S_2$ e $S_3$)"
      ],
      "metadata": {
        "id": "v-dwPKn9eA6-"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def minor_elements_set(c_major, \n",
        "                       c_minor, \n",
        "                       p=2, \n",
        "                       shuffle=False, \n",
        "                       progress=False):\n",
        "    \"\"\"Try to return the minimum no. of elements of c_major that\n",
        "    contains all the elements from c_minor\"\"\"\n",
        "    if shuffle:\n",
        "        random.shuffle(c_major)\n",
        "\n",
        "    c_minor_cp = c2.copy()\n",
        "    c_major_i_is_valid = False\n",
        "    S = []\n",
        "    i = 0\n",
        "    while len(c_minor_cp) > 0:\n",
        "        if progress: print(len(c_minor_cp))\n",
        "        # combinações p a p do elemento c5\n",
        "        c_minor_combs = list(combinations(c_major[i], p))\n",
        "        for minor_comb in c_minor_combs:\n",
        "            # remover os subconjuntos\n",
        "            if minor_comb in c_minor_cp:\n",
        "                c_minor_cp.remove(n)\n",
        "                c_major_i_is_valid = True\n",
        "        # o elemento c5 eliminou ao menos um subconjunto?\n",
        "        if c_major_i_is_valid:\n",
        "            S.append(c_major[i])\n",
        "            c_major_i_is_valid = False\n",
        "        i += 1\n",
        "    return S"
      ],
      "metadata": {
        "id": "q0T3aB19btlq"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Estimando o número de elementos de $S_1$"
      ],
      "metadata": {
        "id": "ttr88fjt6szL"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 6\n",
        "space = range(1,6+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(100_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "[sorted(i) for i in S_min]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NuvMyP8bIpv2",
        "outputId": "32f561d3-da64-4769-a301-6e9c5a62d822"
      },
      "execution_count": 300,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[1, 2, 4, 5, 6], [1, 2, 3, 4, 5], [1, 2, 3, 4, 6]]"
            ]
          },
          "metadata": {},
          "execution_count": 300
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 7\n",
        "space = range(1,7+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(100_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "[sorted(i) for i in S_min]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "yyYisofTJd-H",
        "outputId": "60631fa1-61b9-482c-a87f-e3fb18cfead1"
      },
      "execution_count": 299,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[1, 2, 4, 5, 6], [2, 3, 4, 6, 7], [1, 3, 4, 5, 7]]"
            ]
          },
          "metadata": {},
          "execution_count": 299
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 8\n",
        "space = range(1,8+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(1_000_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "[sorted(i) for i in S_min]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1cpPt2T0MCNx",
        "outputId": "7e33b92e-223a-4c5f-d51d-521bda11fd09"
      },
      "execution_count": 298,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "4\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[1, 3, 5, 6, 7], [2, 3, 4, 5, 8], [1, 2, 4, 7, 8], [1, 2, 4, 6, 8]]"
            ]
          },
          "metadata": {},
          "execution_count": 298
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 9\n",
        "space = range(1,9+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(1_000_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "[sorted(i) for i in S_min]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "gMHpxF_KLReV",
        "outputId": "a4b7b671-1eeb-48eb-c2b4-3687b0a382ee"
      },
      "execution_count": 296,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(1, 2, 3, 4, 8),\n",
              " (1, 5, 6, 7, 9),\n",
              " (2, 4, 5, 6, 8),\n",
              " (2, 4, 7, 8, 9),\n",
              " (3, 5, 6, 7, 9)]"
            ]
          },
          "metadata": {},
          "execution_count": 296
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 10\n",
        "space = range(1,10+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(100_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "[sorted(i) for i in S_min]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rzMiQOkUK1bn",
        "outputId": "68ffe098-0da1-46ac-9f07-2bf8142074cf"
      },
      "execution_count": 301,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "6\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[1, 3, 6, 8, 9],\n",
              " [1, 3, 5, 8, 10],\n",
              " [2, 4, 6, 9, 10],\n",
              " [5, 6, 7, 9, 10],\n",
              " [1, 2, 4, 5, 7],\n",
              " [2, 3, 4, 7, 8]]"
            ]
          },
          "metadata": {},
          "execution_count": 301
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 11\n",
        "space = range(1,11+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(1_000_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "[sorted(i) for i in S_min]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "J1vBjOXrLp26",
        "outputId": "60b3313c-610d-4cf5-f628-7d3b06daa2e2"
      },
      "execution_count": 311,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "8\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[2, 6, 7, 8, 10],\n",
              " [2, 5, 7, 8, 9],\n",
              " [3, 5, 6, 10, 11],\n",
              " [1, 4, 6, 7, 9],\n",
              " [1, 2, 3, 8, 11],\n",
              " [2, 3, 4, 8, 9],\n",
              " [3, 7, 9, 10, 11],\n",
              " [1, 4, 5, 10, 11]]"
            ]
          },
          "metadata": {},
          "execution_count": 311
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 12\n",
        "space = range(1,12+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(1_000_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "[sorted(i) for i in S_min]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "F06yh2Z-MJ92",
        "outputId": "72b12471-7a1c-4ac5-b568-630b32a7bd0d"
      },
      "execution_count": 317,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "11\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[2, 3, 4, 5, 10],\n",
              " [1, 7, 8, 9, 12],\n",
              " [4, 5, 6, 9, 11],\n",
              " [1, 5, 10, 11, 12],\n",
              " [6, 7, 8, 10, 11],\n",
              " [1, 4, 6, 7, 12],\n",
              " [1, 2, 3, 4, 8],\n",
              " [2, 3, 4, 6, 12],\n",
              " [2, 3, 7, 9, 11],\n",
              " [3, 8, 9, 10, 11],\n",
              " [5, 7, 8, 9, 10]]"
            ]
          },
          "metadata": {},
          "execution_count": 317
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 13\n",
        "space = range(1,13+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(1_000_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "S_min"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "OVBA3dW-M5Sc",
        "outputId": "e0b263b0-1297-4996-e360-3713c1a05e9a"
      },
      "execution_count": 322,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "14\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(3, 5, 6, 9, 13),\n",
              " (2, 5, 9, 11, 12),\n",
              " (3, 4, 8, 11, 12),\n",
              " (2, 6, 8, 11, 13),\n",
              " (1, 3, 6, 8, 9),\n",
              " (1, 5, 7, 8, 13),\n",
              " (1, 4, 5, 6, 10),\n",
              " (1, 6, 8, 10, 12),\n",
              " (1, 8, 10, 11, 13),\n",
              " (1, 2, 3, 7, 10),\n",
              " (6, 7, 9, 10, 13),\n",
              " (2, 3, 4, 6, 7),\n",
              " (4, 7, 11, 12, 13),\n",
              " (2, 4, 6, 7, 9)]"
            ]
          },
          "metadata": {},
          "execution_count": 322
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 14\n",
        "space = range(1,14+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(100_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "S_min"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3Fm3rHNlRMZV",
        "outputId": "57e75904-11f8-4400-afa0-93c549241517"
      },
      "execution_count": 258,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "17\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(1, 2, 4, 5, 9),\n",
              " (1, 4, 11, 12, 14),\n",
              " (1, 6, 7, 9, 10),\n",
              " (2, 7, 9, 12, 13),\n",
              " (1, 3, 5, 8, 12),\n",
              " (4, 6, 8, 9, 10),\n",
              " (1, 4, 6, 13, 14),\n",
              " (2, 6, 10, 11, 13),\n",
              " (3, 6, 7, 12, 13),\n",
              " (1, 2, 3, 8, 13),\n",
              " (3, 4, 9, 12, 14),\n",
              " (5, 7, 11, 13, 14),\n",
              " (3, 5, 7, 9, 10),\n",
              " (3, 9, 10, 11, 12),\n",
              " (2, 4, 5, 6, 7),\n",
              " (3, 6, 7, 8, 11),\n",
              " (2, 8, 10, 11, 14)]"
            ]
          },
          "metadata": {},
          "execution_count": 258
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 15\n",
        "space = range(1,15+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(100_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "S_min"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hemRNaPXTmuW",
        "outputId": "5298f187-fb5c-4e66-be5c-b6ab9051be6d"
      },
      "execution_count": 257,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "20\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(6, 9, 10, 11, 13),\n",
              " (2, 5, 9, 12, 15),\n",
              " (2, 3, 4, 9, 14),\n",
              " (2, 5, 6, 12, 14),\n",
              " (1, 2, 4, 8, 11),\n",
              " (4, 7, 10, 12, 13),\n",
              " (1, 6, 7, 9, 15),\n",
              " (3, 8, 9, 12, 13),\n",
              " (5, 8, 13, 14, 15),\n",
              " (2, 3, 10, 11, 14),\n",
              " (2, 7, 10, 11, 15),\n",
              " (4, 6, 11, 14, 15),\n",
              " (1, 2, 8, 13, 14),\n",
              " (1, 3, 6, 12, 15),\n",
              " (3, 4, 5, 11, 12),\n",
              " (2, 7, 9, 12, 14),\n",
              " (1, 8, 10, 12, 14),\n",
              " (2, 5, 8, 10, 15),\n",
              " (1, 3, 5, 7, 9),\n",
              " (3, 6, 7, 8, 12)]"
            ]
          },
          "metadata": {},
          "execution_count": 257
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 16\n",
        "space = range(1,16+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(100_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "S_min"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "O2UTk_WC2uXc",
        "outputId": "5b404287-586b-4b0d-9684-a94f11a1c7a8"
      },
      "execution_count": 243,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "23\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(2, 5, 6, 7, 9),\n",
              " (2, 8, 10, 11, 16),\n",
              " (1, 4, 10, 12, 13),\n",
              " (5, 7, 8, 10, 12),\n",
              " (3, 7, 10, 13, 15),\n",
              " (1, 5, 12, 14, 15),\n",
              " (4, 5, 9, 11, 14),\n",
              " (1, 9, 11, 15, 16),\n",
              " (6, 9, 11, 13, 16),\n",
              " (2, 4, 7, 8, 16),\n",
              " (5, 9, 10, 11, 12),\n",
              " (7, 8, 13, 14, 15),\n",
              " (3, 4, 8, 12, 15),\n",
              " (1, 2, 6, 8, 12),\n",
              " (4, 6, 9, 10, 15),\n",
              " (1, 2, 3, 6, 14),\n",
              " (2, 6, 7, 11, 13),\n",
              " (4, 10, 12, 14, 16),\n",
              " (4, 5, 8, 9, 16),\n",
              " (2, 5, 10, 13, 14),\n",
              " (1, 2, 7, 10, 15),\n",
              " (3, 5, 9, 10, 11),\n",
              " (1, 2, 3, 4, 16)]"
            ]
          },
          "metadata": {},
          "execution_count": 243
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# de 1 a 17\n",
        "space = range(1,17+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))\n",
        "\n",
        "min_len = len(c5)\n",
        "S_min = []\n",
        "for i in range(100_000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S_min = S\n",
        "print(min_len)\n",
        "S_min"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xME1WpQa-ANo",
        "outputId": "d750bf6d-ce4d-4caa-a1a3-d7b978ff8c10"
      },
      "execution_count": 259,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "27\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(2, 6, 7, 11, 14),\n",
              " (4, 5, 11, 12, 14),\n",
              " (1, 4, 9, 10, 16),\n",
              " (5, 7, 9, 15, 16),\n",
              " (1, 3, 4, 7, 13),\n",
              " (2, 4, 9, 16, 17),\n",
              " (3, 4, 7, 8, 11),\n",
              " (3, 7, 10, 16, 17),\n",
              " (2, 3, 6, 15, 16),\n",
              " (11, 12, 13, 15, 16),\n",
              " (6, 7, 13, 14, 17),\n",
              " (2, 5, 6, 13, 17),\n",
              " (3, 9, 14, 16, 17),\n",
              " (1, 2, 3, 6, 7),\n",
              " (2, 4, 6, 11, 12),\n",
              " (3, 5, 10, 13, 14),\n",
              " (6, 8, 9, 14, 17),\n",
              " (3, 6, 7, 8, 16),\n",
              " (1, 2, 3, 9, 12),\n",
              " (1, 10, 14, 15, 16),\n",
              " (2, 4, 9, 13, 14),\n",
              " (1, 6, 9, 10, 13),\n",
              " (1, 4, 8, 15, 17),\n",
              " (1, 5, 8, 11, 12),\n",
              " (8, 10, 12, 13, 14),\n",
              " (2, 8, 9, 10, 11),\n",
              " (7, 10, 11, 12, 17)]"
            ]
          },
          "metadata": {},
          "execution_count": 259
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "x = np.array([5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]) # número de elementos\n",
        "y = np.array([1, 3, 3, 4, 5, 6, 8, 11, 14, 17, 20, 23, 27]) # mínimo len de S"
      ],
      "metadata": {
        "id": "M3sUaXjcNK1r"
      },
      "execution_count": 89,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# degree = 1\n",
        "z = np.polyfit(x, y, 1)\n",
        "function = np.poly1d(z)\n",
        "function(50)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IBLtFF7b4tRc",
        "outputId": "8062a044-16f8-435f-e7f2-55d0f46e31c6"
      },
      "execution_count": 319,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "93.63736263736264"
            ]
          },
          "metadata": {},
          "execution_count": 319
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# degree = 2\n",
        "z = np.polyfit(x, y, 2)\n",
        "function = np.poly1d(z)\n",
        "print(function(50))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IYIJvWnM40sE",
        "outputId": "5e29ddf9-fc0b-4301-e3b3-6b932137e1f9"
      },
      "execution_count": 320,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "334.5164835164839"
            ]
          },
          "metadata": {},
          "execution_count": 320
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# degree = 3\n",
        "z = np.polyfit(x, y, 3)\n",
        "function = np.poly1d(z)\n",
        "function(50)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RzdBl5W641_P",
        "outputId": "a07b5649-0275-41b6-836c-a336a1dcc02e"
      },
      "execution_count": 321,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "283.516483516487"
            ]
          },
          "metadata": {},
          "execution_count": 321
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# algo entre 283 a 334"
      ],
      "metadata": {
        "id": "30rEV9Rl49rR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "plt.plot(x, y);\n",
        "plt.grid(alpha=.4);"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 265
        },
        "id": "g1uUvnEjO2IX",
        "outputId": "d77b33b0-caa2-4541-afd5-1a17c71beac4"
      },
      "execution_count": 92,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ],
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAD4CAYAAAD1jb0+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAeeklEQVR4nO3deXhU5dnH8e/NvsseCAFZZAfZQgB3wYVaW6rdpCpBEHCp3dTW6tvWV1vr2829KmpYFK274loluLRVCQHZA4QlbBOSQNiTkO15/5ixTTHIkMzkzJn8PtfFlZmTSc79OPLj5M5zz5hzDhER8Z8GXhcgIiI1owAXEfEpBbiIiE8pwEVEfEoBLiLiU43q8mQdO3Z0PXv2rMtTnrSysjIaN27sdRm1Fi/rAK0lFsXLOsAfa1m2bNke51ynY4/XaYD37NmTzMzMujzlSQsEAiQmJnpdRq3FyzpAa4lF8bIO8MdazGxbdcfVQhER8SkFuIiITynARUR8SgEuIuJTCnAREZ9SgIuI+JQCXETEpxTgIiJRVFxawZ0L17LvSGnEv7cCXEQkSpxz3PLSSuZ9msOKnfsj/v0V4CIiUfJAejZvrcrlFxMHcH7/zhH//gpwEZEoeHNVgPsXZXP5yG7MOqd3VM6hABcRibBVO/dz8wsrST61Hb+/fChmFpXzKMBFRCJo94ESZszPpGOrpjx29SiaNmoYtXMpwEVEIqS4tIIZ8zM5XFLOk6nJdGzVNKrnq9OXkxURiVeVlY5bXlzJmsABnrg6mYFd20T9nLoCFxGJgAfSs3lrdS63TRzABYMS6uScCnARkVp6Y2WAB9Kz+fbIJGZGacdJdRTgIiK1sHLHfm55Mbjj5J7Lh0Rtx0l1FOAiIjVUlztOqqMAFxGpgS92nBw5Ws5TU6O/46Q6JwxwM+tuZh+Y2TozW2tmPw4dv9PMdpnZitCfS6JfroiI9yorHTe/uII1gQM8OHkEA7pEf8dJdcLZRlgO3OycW25mrYFlZvZ+6HP3Oef+FL3yRERiz/3p2by9eje3XzKACQPrZsdJdU4Y4M65XCA3dPuQmWUB3aJdmIhILFq4MsCD6dl8d1QSM86uux0n1TmpQR4z6wmMAJYAZwI/NLMpQCbBq/R91XzNTGAmQFJSEoFAoJYlR1dhYaHXJUREvKwDtJZYFC/rgJNby7rdR7jl5WyGJbbkxjEdyM3NjWJlJxZ2gJtZK+Bl4CfOuYNm9ihwN+BCH/8MTDv265xzs4HZAMnJyS4xMTESdUeVH2oMR7ysA7SWWBQv64Dw1pJ7oJhfvrOOzm2akTZtHB08+KXlscLahWJmjQmG9wLn3CsAzrk851yFc64SeAJIiV6ZIiLeKSotZ8b8TIqOlvNU6uiYCG8IbxeKAU8BWc65v1Q53rXKwy4D1kS+PBERb1VWOm5+YSVrAwd5cPII+ndp7XVJ/xZOC+VM4GpgtZmtCB27HZhsZsMJtlBygFlRqVBExEP3L9rIO2t2c8clAz3dcVKdcHah/BOobjb07ciXIyISO15fsYsHF2/iu6OSuPbsXl6X8yWaxBQRqcbn2/dx60urSOnZnt9eVrevcRIuBbiIyDEC+4uZ+fQyOrduyqNXjazz1zgJl97QQUSkii92nBSXVvDM9DExs+OkOgpwEZGQykrHz55fybrcgzyVmhxTO06qoxaKiEjIfYs28u7a4I6T8QNia8dJdRTgIiIEd5w8tHgT30tOYvpZsbfjpDoKcBGp9/6946RXe377raExueOkOuqBi0i9lneolBkvriOhTVMeu2oUTRr557pWAS4i9VZRaTk/f2MLJWUVPDtjDO1bNvG6pJPin39qREQi6FBJGdfOy2Tz3mIemjyCfgmxveOkOroCF5F6J/9QCVPTlrIx7xB3XHAq5w/o7HVJNaIAF5F6ZUvBYVLnZLD3cClPpibTr3W51yXVmFooIlJvrNyxn+889ilHjlbw3IyxnNffn1feX9AVuIjUCx9uyOf6Z5bTsXUT5k8bQ6+OLb0uqdYU4CIS915etpNfvLyK/l1aM+ea0XRu3czrkiJCAS4iccs5x+Mfb+Hed9Zz5mkdeOyqUbRu1tjrsiJGAS4icamy0nH3W+uY868cvjkskT99d5ivhnTCoQAXkbhztLyCn72wkrdW5TL9rF7ccclAGjTwx3j8yVCAi0hcOVRSxqynl/HJ5r3ccclAZpzT2+uSokYBLiJxI/9gCalzlpKdd4j7vj+My0YkeV1SVCnARSQubCk4zJS0DAqPlJI2dTTn9OvkdUlRpwAXEd/7fPs+ps/LxIC/zRzL6UltvS6pTijARcTXPlifzw0LltOpdVPmT0uhZxwM6IRLAS4ivvVi5g5ue2U1A7u2Zs7UFDq1jt03II4GBbiI+I5zjkc/2swf3t3A2X078uhVo2jVtP7FWf1bsYj4WmWl46431zH3kxwmDU/kj9+JvwGdcCnARcQ3qg7ozDi7F7/8WnwO6IRLAS4ivnCwpIyZ8zP5bEth3A/ohEsBLiIxL+9gCalpGWwuOMwDVwxn0vBuXpcUE07YODKz7mb2gZmtM7O1Zvbj0PH2Zva+mWWHPraLfrkiUt9sLjjM5X/9hB2FRaRNHa3wriKczn85cLNzbhAwFrjRzAYBtwHpzrm+QHrovohIxHy+fR/fefQTjpZX8PyscZzdN/6nK0/GCQPcOZfrnFseun0IyAK6AZOAeaGHzQO+Fa0iRaT++WB9PpOf+Iw2zRvz8vVnMKTbKV6XFHNOqgduZj2BEcASIME5lxv61G4g4ThfMxOYCZCUlEQgEKhprXWisLDQ6xIiIl7WAVpLLIr2Ot5ct5f/S99O307N+dM3e9P46AECgQNROZefn5OwA9zMWgEvAz9xzh00+8/WHeecMzNX3dc552YDswGSk5NdYmJi7SquA36oMRzxsg7QWmJRNNbhnOOvH27mj4u21+mAjl+fk7D+y5hZY4LhvcA590rocJ6ZdXXO5ZpZVyA/WkWKSPyrqHT87xtrmf/pNi4b0Y3/+/bp9XZAJ1zh7EIx4Ckgyzn3lyqfWgikhm6nAq9HvjwRqQ9Kyiq46bnlzP90G7PO6c2f4/Dtz6IhnCvwM4GrgdVmtiJ07HbgXuAFM5sObAO+F50SRSSeHSgODugs2VrI/3x9INeerQGdcJ0wwJ1z/wSON6s6IbLliEh9UnVA58HJI/jmMH/2or2iSUwR8cSm/MOkpmWwv6iUOVNTOKtvR69L8h0FuIjUuWXb9jF93lIaNWjA87PGaY93DSnARaROpWflceOzy+nSphnzp42hR4cWXpfkWwpwEakzzy/dzu2vrmFIYhuemjqajq3q1zvoRJoCXESizjnHw4s38ef3N3Juv0789cqRtKyH76ATafovKCJRVVHp+M3CNTzz2XYuHxkc0GncUHu8I0EBLiJRU1JWwU/+toJ31+7munP78IuJ/an6MhxSOwpwEYmKA8VlzJiXydJthfz60kFMO6uX1yXFHQW4iERc7oFipqYtZcuewzx4xQi+oQGdqFCAi0hEZecdIjUtg4Ml5cy7JoUzTtOATrQowEUkYpZtK2Ta3EyaNGrA87PGMjhRAzrRpAAXkYh4f10eP3x2OYltmzN/Wgrd22tAJ9oU4CJSa89lbOeOV1cztNsppE0dTQcN6NQJBbiI1JhzjgfTN3Hfoo2c1z84oNOiiWKlrui/tIjUSEWl41evr+HZJdv59sgk7v32UA3o1DEFuIictKPllVz/zDLeW5fHDef14daLNaDjBQW4iJyUA0Vl/OS1TazKPcKd3xjE1DM1oOMVBbiIhC2wv5jUtAxy9hTx0OQRXHq6BnS8pAAXkbBsDA3oHC4p5y+T+ii8Y4ACXEROaGlOIdPnLqVZ44Y8P2scbTnsdUkC6FfGIvKV/r52N1c9uYSOrZry8vVnMCixjdclSYiuwEXkuBYs2cavXlvD6UltSZs6mvYtm3hdklShABeRL3HOcf+ibB5Iz+b8/p14RAM6MUnPiIj8l/KKSn71+lqey9jOd0clcc/lGtCJVQpwEfm3krIKbnru8+ALU51/Gjdf1E8DOjFMAS4iAOwvKmX6vEyWb9/HXZMGM2VcT69LkhNQgIsIgf3FTEnLYPveIh75wUguGdrV65IkDApwkXpuw+7ggM6Ro+XMm5bCuD4dvC5JwqQAF6nHlmzZy4z5mTRv0pAXrhvHwK7a4+0nJ/zVspmlmVm+ma2pcuxOM9tlZitCfy6JbpkiEmnvrtnN1WkZdGodHNBRePtPOHuD5gITqzl+n3NueOjP25EtS0Si6ZnPtnHDgmUMTmzDS9edQVI7vf2ZH52wheKc+9jMeka/FBGJNucc972/kQcXb2LCgM48/IORNG/S0OuypIZq0wP/oZlNATKBm51z+6p7kJnNBGYCJCUlEQgEanHK6CssLPS6hIiIl3WA1hIp5ZWOP36wgzfW7uUbgzpw6/hE9u3Jo9q/uCeg5yQ21DTAHwXuBlzo45+BadU90Dk3G5gNkJyc7BITY/8lKP1QYzjiZR2gtdRWcWkFNz23nEVZe7lp/Gn87MLaD+joOfFejQLcOZf3xW0zewJ4M2IViUhE7TtSyvR5S/l8x37unjSYqzWgEzdqFOBm1tU5lxu6exmw5qseLyLe2LW/mClPLWHHvmIevXIkE4doQCeenDDAzew54Dygo5ntBH4DnGdmwwm2UHKAWVGsUURqYP3ug6SmZVBUWsHT01IY01sDOvEmnF0ok6s5/FQUahGRCPksNKDTskkjXrxuHAO6aI93PNIkpkiceWd1Lj9+fgU92rdg3rQUurVt7nVJEiUKcJE48vSnOfx64VpGdA++g07bFnoHnXimABeJA845/vzeRh7+YBMXDOzMQ5M1oFMfKMBFfK68opLbX13NC5k7mZzSnbsnDaGR3kGnXlCAi/hYcWkFNz67nMXr8/nRhL789IK+egedekQBLuJThaEBnZU79vPbbw3hqrGnel2S1DEFuIgP7SgsInVOBjv3FfPXK0cxcUgXr0sSDyjARXwmKzc4oFNSVsGCa8cwumd7r0sSjyjARXzk0817mTk/k5ZNG/HidWfQv0trr0sSDynARXzirVW5/PT5FZzaITigk6gBnXpPAS7iA/M+yeHON9Yyqkc7nkxN1oCOAApwkZjmnONP723gkQ82c+GgBB6aPIJmjTWgI0EKcJEYVVZRyS9fWc1Ly3YyOaUHd08arAEd+S8KcJEYVFRazo0LlvPBhgJ+ckFffjxBAzryZQpwkRhTeKSUa+YuZfXO/dxz2VB+MKaH1yVJjFKAi8SQHYVFpKZlsGt/MY9dNYqLBmtAR45PAS4SI9YFDpI6J4PS8koWXDuGZA3oyAkowEViwCeb9zBr/jJaNWvEguvG0S9BAzpyYgpwEY+9uSrAz55fSc+OwQGdrqdoQEfCowAX8dCcf23lrjfXkXxqO56cMppTWjT2uiTxEQW4iAecc/zh7xt49MPNXDw4gQeu0ICOnDwFuEgdK6uo5Bcvr+KV5bu4ckwP7po0hIYNtMdbTp4CXKQOFZVWcO28TD7aWMDPLuzHTeNP04CO1JgCXKSO7D18lJte3cSG/CLuvXwoV6RoQEdqRwEuUgd2FBYxJS2DXfuKefzqZC4clOB1SRIHFOAiUbZm1wGmzllKWUUlD11+msJbIkYBLhJF/9q0h1lPL6NNs0b8beY4WpQf8rokiSN6bUqRKFm4MsDUORl0a9ucV244k9M6a7pSIktX4CJR8NQ/t3L3m+tI6dWeJ6Ykc0pzDehI5J3wCtzM0sws38zWVDnW3szeN7Ps0Md20S1TxB8qKx2/fyeLu99cx8TBXZg/LUXhLVETTgtlLjDxmGO3AenOub5Aeui+SL1WVlHJLS+u5PGPtnD12FN55MqRmq6UqDphgDvnPgYKjzk8CZgXuj0P+FaE6xLxlSNHy5k+L5NXPt/FLRf1465JgzVdKVFX0x54gnMuN3R7N3DcfVFmNhOYCZCUlEQgEKjhKetGYeGx/1b5U7ysA2J/LYVFZdyycAvZBUX8ckIPvjGgJbm5udU/NsbXEq54WQf4ey21/iWmc86ZmfuKz88GZgMkJye7xMTE2p4y6vxQYzjiZR0Qu2vZvreIHy5Ywu6DJcyeksyEgSfe4x2razlZ8bIO8O9aahrgeWbW1TmXa2ZdgfxIFiXiB8EBnQzKKx0Lrh3LqFP1u3ypWzXdB74QSA3dTgVej0w5Iv7wz+w9fP/xT2naqCEvXXeGwls8Ec42wueAT4H+ZrbTzKYD9wIXmlk2cEHovki98PqKXVwzN4Pu7Vvwyg1ncFrnVl6XJPXUCVsozrnJx/nUhAjXIhLznvzHFn77VhZjerVntgZ0xGOaxBQJwxcDOk/8YyuXDO3CX743XHu8xXMKcJETKC2v5OcvreS1FQGmjDuV33xDe7wlNijARb7C4aPlXP/MMv6RvYdbL+7PDef10TvoSMxQgIscR8Gho0ybu5R1uQf543dO57vJ3b0uSeS/KMBFqrFt7xGmpGWQd7CEJ6aMYvwAvQmDxB4FuMgxVu88wDVzM6iodDw3YywjemiPt8QmBbhIFR9vLOC6Z5bRrkUT5k9PoU8n7fGW2KUAFwl57fNd3PLiSvomtGbuNaNJaNPM65JEvpICXAR44uMt/O7tLMb17sDjU0bRppkGdCT2KcClXtu1v5jfvrmOd9bs5uund+Uv3xtG00Ya0BF/UIBLvXS0vIIn/7GVhxdvwuG49eL+XH9uHxpoQEd8RAEu9c5HGwu4c+Fatu45wsWDE/jVpYNIatfC67JETpoCXOqNXfuLufuNdby7djc9O7Rg7jWjOa9/Z6/LEqkxBbjEvS/aJQ8tzgbg1ov7c+3ZvdTrFt9TgEtcq9oumTi4C/9z6UC1SyRuKMAlLlVtl/Tq2JJ501I4t18nr8sSiSgFuMQVtUukPlGAS9z4cEM+//vGOrbuOcLXhnThfy4dRLe2zb0uSyRqFODiezv3FXH3m+v4+9o8endsyfxpKZyjdonUAwpw8a2j5RU88fEWHv5gE4apXSL1jgJcfOnDDfncuXAtOXuL1C6ReksBLr6yozDYLnlvndolIgpw8YWSsmC75JEPg+2Sn0/sz/Sz1C6R+k0BLjHv05wDPLRgAzl7i7hkaBfu+LraJSKgAJcYlbPnCOnr8/n72t1kbC2kd8eWPD09hbP7ql0i8gUFuMSE8opKlm3bx+L1+SzKymNzwREA+nZuxY1nJvKjr52udonIMRTg4pkDxWV8tLGAxVl5fLixgP1FZTRuaIzp1YGrxp7KhAEJ9OjQgkAgoPAWqYYCXOrU1j1HSM/KIz0rn6U5hZRXOtq1aMz4AZ25YGACZ/ftSGu9nZlIWBTgElVftEbSQ62RLaHWSL+EVsw4pzcTBnRmRI92NNQ74YictFoFuJnlAIeACqDcOZcciaLE3w4UlfFRdgHpWXl8uKGAA8XB1sjY3h2YMvZUJgxMoHt7vaSrSG1F4gr8fOfcngh8H/GxL1oji7LyWJqzj4pKR/uWTbhgYAITBnZWa0QkCtRCkRopr6gkc9u+f/ezt+wJtkb6J7Rm1jm9mTCwM8O7qzUiEk21DXAHvGdmDnjcOTc7AjVJjDpQVMaHG/NJz8rnww35HCwp/09rZJxaIyJ1rbYBfpZzbpeZdQbeN7P1zrmPqz7AzGYCMwGSkpIIBAK1PGV0FRYWel1CRERqHdv3lfDPrQf4ZOtBVgYOU+GgbbNGnNWrDWf2OoWUHq1p2SS0xa9kP4HA/oict6p4eU4gftYSL+sAf6+lVgHunNsV+phvZq8CKcDHxzxmNjAbIDk52SUmJtbmlHXCDzWGoybrKK+oZGnOPhavr6Y1cm4fJgxMYHj3tnXeGomX5wTiZy3xsg7w71pqHOBm1hJo4Jw7FLp9EXBXxCqTOlNda6RJwwaM6d2e1DN6Mn5AZ7VGRGJQba7AE4BXzeyL7/Osc+7diFQlUbel4DDpWcG92ZnbgrtGOrRswkWDu3DBwM6c1bcTrZrqd9wisazGf0Odc1uAYRGsRaKorKKSzJzQrpH1+WwNtUYGdGnNdef2ZvwAb1ojIlJzusSKY8drjYzt04FrzuzJ+f3VGhHxMwV4nNlccJjFWfm8vXIHq3JXqDUiEsf0N9nnjtca6dOhGded2zu4aySpLQ3UGhGJOwpwH/qiNbIoK5+PqmmNjB/QmQbF+327NUpEwqMA94nNBYdDrzWSz7LQrpGOrZpw8eAuTBiYwFl9O/5XayRQHPmBGhGJLQrwGFVWUcnSnELSs/JZfMyukevP7cOEgZ0ZptaISL2mAI8h+4tK+XBDAYuy8vhoYwGHQq2RcX06MO3Mnpw/oDNJ7bRrRESCFOAecs6xueA/71CTua2QSgcdWzXha0O6MH5A8B1qWmrXiIhUQ8lQRWl5JSVllRSXVkTtHJXOsXLHfhZl5bN4fR45e4sAGNi1DTeefxrjB6g1IiLhUYADh0rKeGBRNvM+zaGswgEro37OJo0acEafDkw/qxfjBybQrW3zqJ9TROJLvQ5w5xwLVwb43VtZFBw+yuUjkkhoXkmbNm2iet5eHVty1mlqjYhI7dTbBNmw+xC/fn0NS7YWcnrSKcyekszw7m0JBALaPy0ivlDvAvxQSRn3L8pm7ic5tG7WiHsuG8r3R3fXiziJiO/UmwB3zvH6igC/ezuLPYePcsXoHvz84v60a9nE69JERGqkXgT4ht2H+NXra8gItUuenJLMsO5tvS5LRKRW4jrA1S4RkXgWlwGudomI1AdxF+BV2yXD1C4RkTgWNwF+bLvk95cP5fvJ3TXRKCJxy/cBfmy7ZHJKD269SO0SEYl/vg7w9bsP8uvX1/67XfJUajKnJ6ldIiL1gy8D/GBJGfe/H3ztkjbNGnHv5UP5ntolIlLP+CrAnXO8tmIX97y9nj2Hj/KDlB7conaJiNRTvgnw9bsP8uvX1pKRU8iw7m3VLhGRes8XAf5Qejb3p2erXSIiUoUvArxHhxZcMbo7t17cn7Yt1C4REQGfBPik4d2YNLyb12WIiMSUBl4XICIiNaMAFxHxqVoFuJlNNLMNZrbJzG6LVFEiInJiNQ5wM2sIPAJ8DRgETDazQZEqTEREvlptrsBTgE3OuS3OuVLgb8CkyJQlIiInUpsA7wbsqHJ/Z+iYiIjUgahvIzSzmcBMgKSkJAKBQLRPWSuFhYVelxAR8bIO0FpiUbysA/y9ltoE+C6ge5X7SaFj/8U5NxuYDZCcnOwSExNrccq64YcawxEv6wCtJRbFyzrAv2sx51zNvtCsEbARmEAwuJcCP3DOrf2KrykAttXohHWnI7DH6yIiIF7WAVpLLIqXdYA/1nKqc67TsQdrfAXunCs3sx8CfwcaAmlfFd6hr/lSAbHGzDKdc8le11Fb8bIO0FpiUbysA/y9llr1wJ1zbwNvR6gWERE5CZrEFBHxKQX4l832uoAIiZd1gNYSi+JlHeDjtdT4l5giIuItXYGLiPiUAlxExKcU4CFm1tbMXjKz9WaWZWbjvK6ppszsp2a21szWmNlzZtbM65rCZWZpZpZvZmuqHGtvZu+bWXboYzsvawzHcdbxx9D/X6vM7FUz88Wbula3liqfu9nMnJl19KK2k3W8tZjZTaHnZq2Z/cGr+k6WAvw/HgDedc4NAIYBWR7XUyNm1g34EZDsnBtCcI/+Fd5WdVLmAhOPOXYbkO6c6wukh+7Hurl8eR3vA0Occ6cTHIL7ZV0XVUNz+fJaMLPuwEXA9rouqBbmcsxazOx8gi/EN8w5Nxj4kwd11YgCHDCzU4BzgKcAnHOlzrn93lZVK42A5qFp2RZAbL8ATRXOuY+BY1+cYhIwL3R7HvCtOi2qBqpbh3PuPedceejuZwRffiLmHec5AbgP+Dngm50Qx1nL9cC9zrmjocfk13lhNaQAD+oFFABzzOxzM3vSzFp6XVRNOOd2EbyC2A7kAgecc+95W1WtJTjnckO3dwMJXhYTIdOAd7wuoqbMbBKwyzm30utaIqAfcLaZLTGzj8xstNcFhUsBHtQIGAk86pwbARzBHz+mf0moPzyJ4D9KiUBLM7vK26oixwX3vfrmiq86ZnYHUA4s8LqWmjCzFsDtwK+9riVCGgHtgbHArcALZmbelhQeBXjQTmCnc25J6P5LBAPdjy4AtjrnCpxzZcArwBke11RbeWbWFSD00Tc/4h7LzKYClwJXOv8OYfQheIGw0sxyCLaClptZF0+rqrmdwCsuKAOoJPgCVzFPAQ4453YDO8ysf+jQBGCdhyXVxnZgrJm1CF1FTMCnv5CtYiGQGrqdCrzuYS01ZmYTCfaMv+mcK/K6nppyzq12znV2zvV0zvUkGIAjQ3+P/Og14HwAM+sHNCH2X50QUIBXdROwwMxWAcOBezyup0ZCP0W8BCwHVhN8jn0zKmxmzwGfAv3NbKeZTQfuBS40s2yCP2Hc62WN4TjOOh4GWgPvm9kKM3vM0yLDdJy1+NJx1pIG9A5tLfwbkOqXn440Si8i4lO6AhcR8SkFuIiITynARUR8SgEuIuJTCnAREZ9SgIuI+JQCXETEp/4fLMqF+TBGLpEAAAAASUVORK5CYII=\n"
          },
          "metadata": {
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **ITEM 02**) Obter o menor conjunto $S_1$ de 5 números que contém todas as combinações de 2 elementos (**PROGRAMA 02**)"
      ],
      "metadata": {
        "id": "n0Ny_weQarc1"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "space = range(1,50+1)\n",
        "c2 = list(combinations(space, 2))\n",
        "c5 = list(combinations(space, 5))"
      ],
      "metadata": {
        "id": "cyP9OLAZifbW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "min_len = len(c5)\n",
        "S1 = []\n",
        "for i in range(1000):\n",
        "    S = minor_elements_set(c5, c2, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S1 = S\n",
        "print(min_len)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RXD00E_FcwnR",
        "outputId": "4e289306-6736-4fd1-8718-38e6d4cdd9be"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "330\n",
            "CPU times: user 39min 56s, sys: 4.35 s, total: 40min\n",
            "Wall time: 40min 7s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "S1 = pd.read_csv('S_c50_2.csv')\n",
        "S1 = list(S1['S'].values)\n",
        "S1 = [literal_eval(s) for s in S1]\n",
        "len(S1)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "cbo5Be7L4WYB",
        "outputId": "76b00745-cd5e-4953-ae3e-af8bae7ebdde"
      },
      "execution_count": 42,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "330"
            ]
          },
          "metadata": {},
          "execution_count": 42
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "S1 = sorted(S1)\n",
        "S1[:10]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Misw_2C5sTKo",
        "outputId": "4a314222-b1c5-478c-a498-b1a3ce8297d4"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(1, 2, 5, 16, 23),\n",
              " (1, 2, 18, 31, 33),\n",
              " (1, 2, 23, 32, 42),\n",
              " (1, 3, 8, 10, 48),\n",
              " (1, 3, 11, 17, 36),\n",
              " (1, 3, 17, 45, 49),\n",
              " (1, 4, 6, 22, 47),\n",
              " (1, 4, 10, 44, 50),\n",
              " (1, 4, 11, 13, 22),\n",
              " (1, 4, 19, 38, 50)]"
            ]
          },
          "metadata": {},
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **ITEM 03**) Obter o menor conjunto $S_2$ de 5 números que contém todas as combinações de 3 elementos (**PROGRAMA 03**)"
      ],
      "metadata": {
        "id": "kDTeX59mXCh0"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "space = range(1,50+1)\n",
        "c3 = list(combinations(space, 3))\n",
        "c5 = list(combinations(space, 5))"
      ],
      "metadata": {
        "id": "Zu7HeKjNAjtY"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "min_len = len(c5)\n",
        "S2 = []\n",
        "for i in range(10):\n",
        "    S = minor_elements_set(c5, c3, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S2 = S\n",
        "print(min_len)"
      ],
      "metadata": {
        "id": "q6MXmjdGAjtZ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "S2 = pd.read_csv('S_c50_3.csv')\n",
        "S2 = list(S2['S'].values)\n",
        "S2 = [literal_eval(s) for s in S2]\n",
        "len(S2)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CNHIj0qgAjtZ",
        "outputId": "b013a935-caba-4596-9f0d-a2da04d58226"
      },
      "execution_count": 43,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5698"
            ]
          },
          "metadata": {},
          "execution_count": 43
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "S2 = sorted(S2)\n",
        "S2[:10]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4a314222-b1c5-478c-a498-b1a3ce8297d4",
        "id": "Fk-8GhEzAjtZ"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(1, 2, 5, 16, 23),\n",
              " (1, 2, 18, 31, 33),\n",
              " (1, 2, 23, 32, 42),\n",
              " (1, 3, 8, 10, 48),\n",
              " (1, 3, 11, 17, 36),\n",
              " (1, 3, 17, 45, 49),\n",
              " (1, 4, 6, 22, 47),\n",
              " (1, 4, 10, 44, 50),\n",
              " (1, 4, 11, 13, 22),\n",
              " (1, 4, 19, 38, 50)]"
            ]
          },
          "metadata": {},
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **ITEM 04**) Obter o menor conjunto $S_3$ de 5 números que contém todas as combinações de 4 elementos (**PROGRAMA 04**)"
      ],
      "metadata": {
        "id": "HneCNzbQXI56"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "space = range(1,50+1)\n",
        "c4 = list(combinations(space, 4))\n",
        "c5 = list(combinations(space, 5))"
      ],
      "metadata": {
        "id": "CvKhD0eUA0Zn"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "min_len = len(c5)\n",
        "S3 = []\n",
        "for i in range(1):\n",
        "    S = minor_elements_set(c5, c4, shuffle=True)\n",
        "    if len(S) < min_len:\n",
        "        min_len = len(S)\n",
        "        S3 = S\n",
        "print(min_len)"
      ],
      "metadata": {
        "id": "lLveHfJMA0Zo"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "S3 = pd.read_csv('S_c50_4.csv')\n",
        "S3 = list(S3['S'].values)\n",
        "S3 = [literal_eval(s) for s in S3]\n",
        "len(S3)"
      ],
      "metadata": {
        "id": "XqsElR1_-67H",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "bea67927-25c2-4949-e14b-e83d50f1fec4"
      },
      "execution_count": 44,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "103933"
            ]
          },
          "metadata": {},
          "execution_count": 44
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "S2 = sorted(S2)\n",
        "S2[:10]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4a314222-b1c5-478c-a498-b1a3ce8297d4",
        "id": "GdwzVHWMA9CY"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(1, 2, 5, 16, 23),\n",
              " (1, 2, 18, 31, 33),\n",
              " (1, 2, 23, 32, 42),\n",
              " (1, 3, 8, 10, 48),\n",
              " (1, 3, 11, 17, 36),\n",
              " (1, 3, 17, 45, 49),\n",
              " (1, 4, 6, 22, 47),\n",
              " (1, 4, 10, 44, 50),\n",
              " (1, 4, 11, 13, 22),\n",
              " (1, 4, 19, 38, 50)]"
            ]
          },
          "metadata": {},
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **ALGORITMO** de `Backtesting`"
      ],
      "metadata": {
        "id": "xWqiU2-2t74F"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def backtest(S, \n",
        "             df_results,\n",
        "             split=None, \n",
        "             budget=100_000,\n",
        "             seed=None, \n",
        "             shuffle=False, \n",
        "             show_hits=False, \n",
        "             show_summary=False,\n",
        "             prize_2=4.16,\n",
        "             prize_3=11.89,\n",
        "             prize_4=82.31,\n",
        "             prize_5='Jackpot'):\n",
        "    \n",
        "    \"\"\"Runs a backtest on the given historical data of euro millions,\n",
        "    based on the given set of bets\"\"\"\n",
        "    retorno = 0\n",
        "\n",
        "    prizes = {\n",
        "        0: 0,\n",
        "        1: 0,\n",
        "        2: prize_2,\n",
        "        3: prize_3,\n",
        "        4: prize_4 \n",
        "    }\n",
        "\n",
        "    summary = {\n",
        "        0: 0,\n",
        "        1: 0,\n",
        "        2: 0,\n",
        "        3: 0,\n",
        "        4: 0,\n",
        "        5: 0\n",
        "    }\n",
        "\n",
        "    if seed:\n",
        "        random.seed(seed)\n",
        "\n",
        "    if shuffle:\n",
        "        random.shuffle(S)\n",
        "    \n",
        "    if split:\n",
        "        S = S[:int(len(S)*split)]\n",
        "    \n",
        "    for row in df_results.iterrows():\n",
        "        sorteio = row[1]\n",
        "\n",
        "        if prize_5 == 'Jackpot':\n",
        "            prizes[5] = sorteio['Jackpot']\n",
        "        else:\n",
        "            prizes[5] = prize_5\n",
        "\n",
        "        resultado = (\n",
        "            sorteio['B1'],\n",
        "            sorteio['B2'],\n",
        "            sorteio['B3'],\n",
        "            sorteio['B4'],\n",
        "            sorteio['B5']\n",
        "        )\n",
        "\n",
        "        for aposta in S:\n",
        "            acertos = 0\n",
        "            for i in aposta:\n",
        "                if i in resultado:\n",
        "                    acertos += 1\n",
        "\n",
        "            # contando duplas, trinas, quadras, etc\n",
        "            for n_acertos in range(1,acertos+1):\n",
        "                retorno += prizes[n_acertos]\n",
        "                summary[n_acertos] += 1\n",
        "\n",
        "            if acertos >= 2 and show_hits:\n",
        "                print('Aposta =', aposta)\n",
        "                print('Resultado =', resultado)\n",
        "                print('Número de acertos =', acertos)\n",
        "                print('Prêmio =', prizes[acertos])\n",
        "                print('Retorno acumulado =', retorno, end='\\n\\n')\n",
        "\n",
        "    if show_summary:\n",
        "        print(f'Sumário')\n",
        "        print('-'*60)\n",
        "        print('Valor investido (€) =', budget)\n",
        "        print('Quantidade total de apostas por sorteio =', len(S))\n",
        "        print('Quantidade total de 0 acertos =', summary[0])\n",
        "        print('Quantidade total de 1 acertos =', summary[1])\n",
        "        print('Quantidade total de 2 acertos =', summary[2])\n",
        "        print('Quantidade total de 3 acertos =', summary[3])\n",
        "        print('Quantidade total de 4 acertos =', summary[4])\n",
        "        print('Quantidade total de 5 acertos =', summary[5])\n",
        "        print('Retorno total (€) =', retorno)\n",
        "        print('Lucro total (€) =', retorno - budget)\n",
        "\n",
        "    return retorno"
      ],
      "metadata": {
        "id": "WPwmxTlXvk0y"
      },
      "execution_count": 46,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# carregando a base de concursos\n",
        "df = pd.read_csv('euro_concursos.csv')\n",
        "print(df.shape)\n",
        "df.head()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 223
        },
        "id": "ZWsYy5DCPRQ9",
        "outputId": "f8b062e0-601d-4371-dd1b-e2bab66f2e92"
      },
      "execution_count": 48,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(1404, 10)\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "   No  B1  B2  B3  B4  B5  LS1  LS2   Jackpot  Wins\n",
              "0   1  16  29  32  36  41    7    9  10143000     1\n",
              "1   2   7  13  39  47  50    2    5  10111500     0\n",
              "2   3  14  18  19  31  37    4    5  11880304     0\n",
              "3   4   4   7  33  37  39    1    5  13870849     1\n",
              "4   5  15  24  28  44  47    4    5  10171500     0"
            ],
            "text/html": [
              "\n",
              "  <div id=\"df-92029466-f786-428e-9858-0d9280fef7c6\">\n",
              "    <div class=\"colab-df-container\">\n",
              "      <div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>No</th>\n",
              "      <th>B1</th>\n",
              "      <th>B2</th>\n",
              "      <th>B3</th>\n",
              "      <th>B4</th>\n",
              "      <th>B5</th>\n",
              "      <th>LS1</th>\n",
              "      <th>LS2</th>\n",
              "      <th>Jackpot</th>\n",
              "      <th>Wins</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>1</td>\n",
              "      <td>16</td>\n",
              "      <td>29</td>\n",
              "      <td>32</td>\n",
              "      <td>36</td>\n",
              "      <td>41</td>\n",
              "      <td>7</td>\n",
              "      <td>9</td>\n",
              "      <td>10143000</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>2</td>\n",
              "      <td>7</td>\n",
              "      <td>13</td>\n",
              "      <td>39</td>\n",
              "      <td>47</td>\n",
              "      <td>50</td>\n",
              "      <td>2</td>\n",
              "      <td>5</td>\n",
              "      <td>10111500</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>3</td>\n",
              "      <td>14</td>\n",
              "      <td>18</td>\n",
              "      <td>19</td>\n",
              "      <td>31</td>\n",
              "      <td>37</td>\n",
              "      <td>4</td>\n",
              "      <td>5</td>\n",
              "      <td>11880304</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>4</td>\n",
              "      <td>4</td>\n",
              "      <td>7</td>\n",
              "      <td>33</td>\n",
              "      <td>37</td>\n",
              "      <td>39</td>\n",
              "      <td>1</td>\n",
              "      <td>5</td>\n",
              "      <td>13870849</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>5</td>\n",
              "      <td>15</td>\n",
              "      <td>24</td>\n",
              "      <td>28</td>\n",
              "      <td>44</td>\n",
              "      <td>47</td>\n",
              "      <td>4</td>\n",
              "      <td>5</td>\n",
              "      <td>10171500</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>\n",
              "      <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-92029466-f786-428e-9858-0d9280fef7c6')\"\n",
              "              title=\"Convert this dataframe to an interactive table.\"\n",
              "              style=\"display:none;\">\n",
              "        \n",
              "  <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
              "       width=\"24px\">\n",
              "    <path d=\"M0 0h24v24H0V0z\" fill=\"none\"/>\n",
              "    <path d=\"M18.56 5.44l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94zm-11 1L8.5 8.5l.94-2.06 2.06-.94-2.06-.94L8.5 2.5l-.94 2.06-2.06.94zm10 10l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94z\"/><path d=\"M17.41 7.96l-1.37-1.37c-.4-.4-.92-.59-1.43-.59-.52 0-1.04.2-1.43.59L10.3 9.45l-7.72 7.72c-.78.78-.78 2.05 0 2.83L4 21.41c.39.39.9.59 1.41.59.51 0 1.02-.2 1.41-.59l7.78-7.78 2.81-2.81c.8-.78.8-2.07 0-2.86zM5.41 20L4 18.59l7.72-7.72 1.47 1.35L5.41 20z\"/>\n",
              "  </svg>\n",
              "      </button>\n",
              "      \n",
              "  <style>\n",
              "    .colab-df-container {\n",
              "      display:flex;\n",
              "      flex-wrap:wrap;\n",
              "      gap: 12px;\n",
              "    }\n",
              "\n",
              "    .colab-df-convert {\n",
              "      background-color: #E8F0FE;\n",
              "      border: none;\n",
              "      border-radius: 50%;\n",
              "      cursor: pointer;\n",
              "      display: none;\n",
              "      fill: #1967D2;\n",
              "      height: 32px;\n",
              "      padding: 0 0 0 0;\n",
              "      width: 32px;\n",
              "    }\n",
              "\n",
              "    .colab-df-convert:hover {\n",
              "      background-color: #E2EBFA;\n",
              "      box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
              "      fill: #174EA6;\n",
              "    }\n",
              "\n",
              "    [theme=dark] .colab-df-convert {\n",
              "      background-color: #3B4455;\n",
              "      fill: #D2E3FC;\n",
              "    }\n",
              "\n",
              "    [theme=dark] .colab-df-convert:hover {\n",
              "      background-color: #434B5C;\n",
              "      box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
              "      filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
              "      fill: #FFFFFF;\n",
              "    }\n",
              "  </style>\n",
              "\n",
              "      <script>\n",
              "        const buttonEl =\n",
              "          document.querySelector('#df-92029466-f786-428e-9858-0d9280fef7c6 button.colab-df-convert');\n",
              "        buttonEl.style.display =\n",
              "          google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
              "\n",
              "        async function convertToInteractive(key) {\n",
              "          const element = document.querySelector('#df-92029466-f786-428e-9858-0d9280fef7c6');\n",
              "          const dataTable =\n",
              "            await google.colab.kernel.invokeFunction('convertToInteractive',\n",
              "                                                     [key], {});\n",
              "          if (!dataTable) return;\n",
              "\n",
              "          const docLinkHtml = 'Like what you see? Visit the ' +\n",
              "            '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
              "            + ' to learn more about interactive tables.';\n",
              "          element.innerHTML = '';\n",
              "          dataTable['output_type'] = 'display_data';\n",
              "          await google.colab.output.renderOutput(dataTable, element);\n",
              "          const docLink = document.createElement('div');\n",
              "          docLink.innerHTML = docLinkHtml;\n",
              "          element.appendChild(docLink);\n",
              "        }\n",
              "      </script>\n",
              "    </div>\n",
              "  </div>\n",
              "  "
            ]
          },
          "metadata": {},
          "execution_count": 48
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **ITEM 05**) Apostar 20% de $S_1$, $S_2$ e $S_3$, para cada um dos cenários $C_1$, $C_2$ e $C_3$"
      ],
      "metadata": {
        "id": "DUrhs_m2zU4h"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## $a$) **PROGRAMA 05**: Se acertou 2 números, então a remuneração é de $4,16$ $€$\n",
        "## $b$) **PROGRAMA 06**: Se acertou 3 números, então a remuneração é de $11,89$ $€$\n",
        "## $c$) **PROGRAMA 07**: Se acertou 4 números, então a remuneração é de $82,31$ $€$\n",
        "## $d$) **PROGRAMA 08**: Se acertou 5 números, então a remuneração é o *Jackpot*"
      ],
      "metadata": {
        "id": "xqHf6f7fPM1n"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **CENÁRIO 01** ($C_1$): Apostando 20% de $S_1$"
      ],
      "metadata": {
        "id": "MtTwX9Zd9i1P"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "retorno_c1 = backtest(S1.copy(), \n",
        "                      df,\n",
        "                      budget=2*1404*len(S1),\n",
        "                      split=.2,\n",
        "                      shuffle=True,\n",
        "                      show_hits=False,\n",
        "                      show_summary=True)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "QY1F-a-guIfa",
        "outputId": "51fd23cc-e91d-4d20-838f-3d0ce797d907"
      },
      "execution_count": 71,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Sumário\n",
            "------------------------------------------------------------\n",
            "Valor investido (€) = 926640\n",
            "Quantidade total de apostas por sorteio = 66\n",
            "Quantidade total de 0 acertos = 0\n",
            "Quantidade total de 1 acertos = 39272\n",
            "Quantidade total de 2 acertos = 6562\n",
            "Quantidade total de 3 acertos = 482\n",
            "Quantidade total de 4 acertos = 13\n",
            "Quantidade total de 5 acertos = 0\n",
            "Retorno total (€) = 34098.92999999991\n",
            "Lucro total (€) = -892541.0700000001\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **CENÁRIO 02** ($C_2$): Apostando 20% de $S_2$"
      ],
      "metadata": {
        "id": "39E36XoP96Gz"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "retorno_c2 = backtest(S2.copy(), \n",
        "                      df,\n",
        "                      budget=2*1404*len(S2),\n",
        "                      split=.2,\n",
        "                      shuffle=True,\n",
        "                      show_hits=False,\n",
        "                      show_summary=True)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "KsMue_2m9V_M",
        "outputId": "7f80e225-cd84-4d7c-de20-4404115bf47b"
      },
      "execution_count": 72,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Sumário\n",
            "------------------------------------------------------------\n",
            "Valor investido (€) = 15999984\n",
            "Quantidade total de apostas por sorteio = 1139\n",
            "Quantidade total de 0 acertos = 0\n",
            "Quantidade total de 1 acertos = 677646\n",
            "Quantidade total de 2 acertos = 114981\n",
            "Quantidade total de 3 acertos = 7553\n",
            "Quantidade total de 4 acertos = 187\n",
            "Quantidade total de 5 acertos = 1\n",
            "Retorno total (€) = 27006854.100000586\n",
            "Lucro total (€) = 11006870.100000586\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **CENÁRIO 03** ($C_3$): Apostando 20% de $S_3$"
      ],
      "metadata": {
        "id": "BZwGoTac-AEa"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "retorno_c3 = backtest(S3.copy(), \n",
        "                      df,\n",
        "                      budget=2*1404*len(S3),\n",
        "                      split=.2,\n",
        "                      shuffle=True,\n",
        "                      show_hits=False,\n",
        "                      show_summary=True)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8RyznhG0-AEb",
        "outputId": "f646469a-e5bd-4950-b85a-0cc7d0dbd2b4"
      },
      "execution_count": 73,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Sumário\n",
            "------------------------------------------------------------\n",
            "Valor investido (€) = 291843864\n",
            "Quantidade total de apostas por sorteio = 20786\n",
            "Quantidade total de 0 acertos = 0\n",
            "Quantidade total de 1 acertos = 12351342\n",
            "Quantidade total de 2 acertos = 2092884\n",
            "Quantidade total de 3 acertos = 139097\n",
            "Quantidade total de 4 acertos = 3041\n",
            "Quantidade total de 5 acertos = 13\n",
            "Retorno total (€) = 831085975.4779832\n",
            "Lucro total (€) = 539242111.4779832\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **SUMÁRIO**"
      ],
      "metadata": {
        "id": "Y6ehgAbp-ZvT"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print('Retorno para C1 (€) =', round(retorno_c1, 3))\n",
        "print('Lucro para C1 (€) =', round((retorno_c1 - 2*1404*len(S1)), 3), end='\\n\\n')\n",
        "\n",
        "print('Retorno para C2 (€) =', round(retorno_c2, 3))\n",
        "print('Lucro para C1 (€) =', round((retorno_c2 - 2*1404*len(S2)), 3), end='\\n\\n')\n",
        "\n",
        "print('Retorno para C3 (€) =', round(retorno_c3, 3))\n",
        "print('Lucro para C1 (€) =', round((retorno_c3 - 2*1404*len(S3)), 3), end='\\n\\n')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "faedae36-5f41-4f26-92b2-84d70f79089e",
        "id": "nOWt2XWF-KA-"
      },
      "execution_count": 77,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Retorno para C1 (€) = 34098.93\n",
            "Lucro para C1 (€) = -892541.07\n",
            "\n",
            "Retorno para C2 (€) = 27006854.1\n",
            "Lucro para C1 (€) = 11006870.1\n",
            "\n",
            "Retorno para C3 (€) = 831085975.478\n",
            "Lucro para C1 (€) = 539242111.478\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **ITEM 06**) Realizando o *Backtest* (**PROGRAMA 09**)"
      ],
      "metadata": {
        "id": "v3Qiy0zsQLln"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **CENÁRIO 01** ($C_1$): Apostando utilizando $S_1$"
      ],
      "metadata": {
        "id": "CqzCTrQq_Mrt"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "retorno_c1 = backtest(S1.copy(), \n",
        "                      df,\n",
        "                      budget=2*1404*len(S1),\n",
        "                      show_hits=False,\n",
        "                      show_summary=True)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "UGEMWUaxR8vi",
        "outputId": "21f9a5b7-94d9-45a5-825c-db5d7647db42"
      },
      "execution_count": 82,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Sumário\n",
            "------------------------------------------------------------\n",
            "Valor investido (€) = 926640\n",
            "Quantidade total de apostas por sorteio = 330\n",
            "Quantidade total de 0 acertos = 0\n",
            "Quantidade total de 1 acertos = 195950\n",
            "Quantidade total de 2 acertos = 33375\n",
            "Quantidade total de 3 acertos = 2268\n",
            "Quantidade total de 4 acertos = 69\n",
            "Quantidade total de 5 acertos = 0\n",
            "Retorno total (€) = 171485.91000010015\n",
            "Lucro total (€) = -755154.0899998999\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **CENÁRIO 02** ($C_2$): Apostando utilizando $S_2$"
      ],
      "metadata": {
        "id": "6XdnWT3T_FPL"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "retorno_c2 = backtest(S2.copy(), \n",
        "                      df,\n",
        "                      budget=2*1404*len(S2),\n",
        "                      show_hits=False,\n",
        "                      show_summary=True)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "03ab04d4-5654-43e0-c71d-fc1e4babb2db",
        "id": "g7avgtbD_FPO"
      },
      "execution_count": 83,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Sumário\n",
            "------------------------------------------------------------\n",
            "Valor investido (€) = 15999984\n",
            "Quantidade total de apostas por sorteio = 5698\n",
            "Quantidade total de 0 acertos = 0\n",
            "Quantidade total de 1 acertos = 3387415\n",
            "Quantidade total de 2 acertos = 574041\n",
            "Quantidade total de 3 acertos = 38256\n",
            "Quantidade total de 4 acertos = 869\n",
            "Quantidade total de 5 acertos = 4\n",
            "Retorno total (€) = 170400588.7897433\n",
            "Lucro total (€) = 154400604.7897433\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **CENÁRIO 03** ($C_3$): Apostando utilizando $S_3$"
      ],
      "metadata": {
        "id": "DgNqxmBG_UDp"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "retorno_c3 = backtest(S3.copy(), \n",
        "                      df,\n",
        "                      budget=2*1404*len(S3),\n",
        "                      show_hits=False,\n",
        "                      show_summary=True)"
      ],
      "metadata": {
        "id": "_Mpk7y5f_WjS"
      },
      "execution_count": 81,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **SUMÁRIO**"
      ],
      "metadata": {
        "id": "yClmvVJj_bDH"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print('Retorno para C1 (€) =', round(retorno_c1, 3))\n",
        "print('Lucro para C1 (€) =', round((retorno_c1 - 2*1404*len(S1)), 3), end='\\n\\n')\n",
        "\n",
        "print('Retorno para C2 (€) =', round(retorno_c2, 3))\n",
        "print('Lucro para C1 (€) =', round((retorno_c2 - 2*1404*len(S2)), 3), end='\\n\\n')\n",
        "\n",
        "print('Retorno para C3 (€) =', round(retorno_c3, 3))\n",
        "print('Lucro para C1 (€) =', round((retorno_c3 - 2*1404*len(S3)), 3), end='\\n\\n')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6bad593e-de53-405f-ce6e-4b2b4fa5d790",
        "id": "iT3hyRpa_bDI"
      },
      "execution_count": 84,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Retorno para C1 (€) = 171485.91\n",
            "Lucro para C1 (€) = -755154.09\n",
            "\n",
            "Retorno para C2 (€) = 170400588.79\n",
            "Lucro para C1 (€) = 154400604.79\n",
            "\n",
            "Retorno para C3 (€) = 3908421818.004\n",
            "Lucro para C1 (€) = 3616577954.004\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **ITEM 07**) Análise de Complexidade"
      ],
      "metadata": {
        "id": "-RbyKQ_tITgm"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **PROGRAMA 01**"
      ],
      "metadata": {
        "id": "hDuFOIP2I4vt"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **PROGRAMA 02**, **PROGRAMA 03** e **PROGRAMA 04**"
      ],
      "metadata": {
        "id": "oRgNhy5xI7ZP"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# versão resumida do algoritmo\n",
        "# _minor_elements_set = O(n²)\n",
        "def _minor_elements_set(c_major, c_minor, p=2):\n",
        "    random.shuffle(c_major)                      # C1 x 1\n",
        "    cond = False                                 # C2 x 1\n",
        "    S = []                                       # C3 x 1\n",
        "    i = 0                                        # C4 x 1\n",
        "    while len(c_minor) > 0:                      # C5 x (1 < k < n) +1\n",
        "        c = list(combinations(c_major[i], p))    # C6 x (1 < k < n)\n",
        "        for n in c:                              # C7 x (1 < k < n)² +1\n",
        "            if n in c_minor:                     # C8 x (1 < k < n)²\n",
        "                c_minor.remove(n)                # C9 x (len(c5) - k)²\n",
        "                cond = True                      # C10 x (len(c5) - k)²\n",
        "        if cond:                                 # C10 x (1 < k < n)\n",
        "            S.append(c_major[i])                 # C12 x (len(c5) - k)\n",
        "            cond = False                         # C13 x (len(c5) - k)\n",
        "        i += 1                                   # C14 x (1 < k < n)\n",
        "    return S                                     # C15 x 1"
      ],
      "metadata": {
        "id": "oGVi0V_mOPmB"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Total de intruções executadas $T_n$\n",
        "\n",
        "$$ T_n = 3k + (k+1) + (k+1)^2 + 2(n-k)^2  $$\n",
        "$$ T_n = 4k + 1 + k^2 + 2k + 1 + 2((n-k)^2) $$\n",
        "$$ T_n = 6k + 2 + k^2 + 2(n^2 -2nk + k^2) $$\n",
        "$$ T_n = 6k + 2 + k^2 + 2n^2 -4nk + 2k^2 $$\n",
        "$$ T_n = 6k + 2 + 3k^2 + 2n^2 -4nk $$\n",
        "$$ T_n = 3k^2 + 2n^2 -4nk + 6k + 2 $$\n",
        "\n",
        "$f(n)$ pertence a $O(n^2)$?\n",
        "\n",
        "$$ c_1 g(n) \\geq f(n) $$\n",
        "$$ c_1 n^2 \\geq 3k^2 + 2n^2 -4nk + 6k + 2 $$\n",
        "$$ c_1 = 6, \\ n_0 = 1 $$\n",
        "$$ f(n) = O(n^2) $$\n",
        "\n",
        "$f(n)$ pertence a $\\Omega(n^2)$?\n",
        "\n",
        "$$ c_2 g(n) \\leq f(n) $$\n",
        "$$ c_2 n^2 \\leq 3k^2 + 2n^2 -4nk + 6k + 2 $$\n",
        "$$ c_2 = 1, \\ n_0 = 1 $$\n",
        "$$ f(n) = \\Omega(n^2) $$\n",
        "\n",
        "Portanto, $f(n) = \\Theta(n^2)$\n"
      ],
      "metadata": {
        "id": "GLHYK19K_xS_"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **PROGRAMA 05, 06, 07, 08** e **09**"
      ],
      "metadata": {
        "id": "szacxDUoJQ7q"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# versão resumida do algoritmo\n",
        "# _minor_elements_set = O(n³)\n",
        "def _backtest(S, df_results, budget=100_000):\n",
        "    prizes = {0:0, 1:0, 2:4.16, 3:11.89, 4:82.31}       # C1 x 1\n",
        "    summary = {0:0, 1:0, 2:0, 3:0, 4:0, 5:0}            # C2 x 1\n",
        "    random.shuffle(S)                                   # C3 x 1\n",
        "    retorno = 0                                         # C4 x 1                         \n",
        "    for row in df_results.iterrows():                   # C5 x n +1\n",
        "        sorteio = row[1]                                # C6 x n   \n",
        "        prizes[5] = sorteio['Jackpot']                  # C7 x n\n",
        "\n",
        "        resultado = (                                   # C8 x n                      \n",
        "            sorteio['B1'], sorteio['B2'],\n",
        "            sorteio['B3'], sorteio['B4'],\n",
        "            sorteio['B5']\n",
        "        )\n",
        "\n",
        "        for aposta in S:                                # C9 x n +1\n",
        "            acertos = 0                                 # C10 x n²\n",
        "            for i in aposta:                            # C11 x n³ +1\n",
        "                if i in resultado:                      # C12 x n³\n",
        "                    acertos += 1                        # C13 x n³\n",
        "            for n_acertos in range(1, acertos+1):       # C14 x n³ +1\n",
        "                retorno += prizes[n_acertos]            # C15 x n³\n",
        "                summary[n_acertos] += 1                 # C16 x n³\n",
        "    return retorno                                      # C17 x 1"
      ],
      "metadata": {
        "id": "pc30fYF7OP_H"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Total de intruções executadas $T_n$\n",
        "\n",
        "$$T_n = 2(n+1) + 3n + n^2 + 4(n^3) + 2(n^3+1)$$\n",
        "$$ T_n = 2n + 2 + 3n + n^2 + 4n^3 + 2n^3 + 2 $$\n",
        "$$ T_n = 5n + 4 + n^2 + 6n^3 $$\n",
        "$$ T_n = 6n^3 + n^2 + 5n + 4 $$\n",
        "\n",
        "$f(n)$ pertence a $O(n^3)$?\n",
        "\n",
        "$$ f(n) = O(n^3) $$\n",
        "$$ c_1 g(n) \\geq f(n) $$\n",
        "$$ c_1 n^3 \\geq 6n^3 + n^2 + 5n + 4 $$\n",
        "$$ c_1 = 7, \\ n_0 = 1 $$\n",
        "$$ f(n) = O(n^3) $$\n",
        "\n",
        "$f(n)$ pertence a $\\Omega(n^3)$?\n",
        "\n",
        "$$ f(n) = O(n^3) $$\n",
        "$$ c_2 g(n) \\leq f(n) $$\n",
        "$$ c_2 n^3 \\leq 6n^3 + n^2 + 5n + 4 $$\n",
        "$$ c_2 = 5, \\ n_0 = 1 $$\n",
        "$$ f(n) = \\Omega(n^3) $$\n",
        "\n",
        "Portanto, $f(n) = \\Theta(n^3)$"
      ],
      "metadata": {
        "id": "nJtPGY2o773h"
      }
    }
  ]
}