p1/izzivi/06 ogrlice/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Naloga\n",
    "\n",
    "## Za programerje\n",
    "\n",
    "Detektiv je osem dni opazoval osumljenko. Prvi dan je nosila ogrlico s črkami WUMYDSR (na sliki). Drugi dan ZQRKJPIZ. Tretji DCYMSLWZ ... No, povejmo kar za vseh osem:\n",
    "\n",
    "<img style=\"float: left; padding-right: 20px\"  src=\"data:image/.png;base64,iVBORw0KGgoAAAANSUhEUgAAAJYAAACWCAMAAAAL34HQAAAAGXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAADlQTFRFYGBgQEBAv7+/7+/vn5+fMDAwgICAEBAQ39/fz8/PcHBwICAgr6+vj4+PUFBQf39/AAAA////////u2S8ewAAABN0Uk5T////////////////////////ALJ93AgAAAl/SURBVHja7Jxrm6soDICDgNzUpv3/P3a5qaCo1LG2z+76pWc6Z/Q1hCSEBHj95AX/Y92K1WmyvHTzbSzFEVdY9iv1VSwlREufy4u2QqgvYlEj1LN0KWHo97Ae2D3LF8P+e1icOwQY/Di2pPUjOID7MPx7WOhAGkTmxg0RlZcTNvZD45exJKKTT2ux3I+AKP2PX8Z6GnRjaS0FEv9pnj+BZeVDn9RCxU/4DSyvTZ3VLLQTM2raD2BJp1TajiRH7VRM/gaWVS7ikRwaCar1C1iAQsYBpCKo1tewVE8wYlnl0oj2H/6TRSwkvfwUlgJhJz5ni6+lNog4YlldN9442BEMNjWYMfv1Y0nGnCERIP+E9bDTvW0tA6HLW6MYWMR6OvTefvbu62fEYoP7Gkn6StSC67YdrEz/gAVIZHwIH7noQ/j37Wbdeg7R8TgHNDxn3eq8rMVj+lse/0LyfS7Yp4I5IghcElIJjFhWuUyck1G1RpWnjMxgloqNIdk+F9RRRa4gqVkxDI+/1SRolCI6fsP5rJ4RLKE64oJKKs/FcqjXS/tgoXQ1+EgmiAdjKdUBF9RS+ZHKoezzBKdFKhu2ZtFpGHuW/58dLqimCr5vOd3RlOTVGOyWC6SUSvtYe4cLDqhUz+hzqffp0wRyO+Ozy9oTsaTK9ArifN3mgn0q7ZSi2eOiztgvLtLTA6qok5tcsEvlNcI6vIRLn3ImekF1ZCfggKrtSDDgz9FwnvFzcjSyC6pNLii+2kRl/97GBG2yADy10OpRlam2uApYXXw1iH9vMF2ipvaoPiAQ0xxMqNQQ52NTg2UMjSGAF1qPpm+bSb1wOIFFyGRlEyoR3DoVvAJLRVVqwx1UnF2m/4O0NM5D2M9UU8Qoj7EmPfBaoMQ07VWYiuwEFhuTAmSMezxVdBHNyvYWsB6YaqfwWt9pEt7MOpVTKRTBx1uaFVVpBKDwZtmsyV0QnBKWGwIYdYutqKqkpRJ7sJzN1qCdDc5nt8FCFDs7eV2jWy/r/De4zlNlJto4fSXTQ6ggNQaiSV7Ec3UXUC0dGqT2tMpuvdiCy1xBNXM1QIbmfSu/4oJLqIoh3Ds+ccGlLqIqcb0VQSy4rqJac70Zb7kbZFzXUC25LBW8FZ3KzLBcRpVzWSobYr6DNaDoZ67rqFIuS2WXnfAGlvURD6dfTVyYX7lhNSYQGqdXDxsB1GMRdJsQzK1qNMdTscxuuoW09raCOR+OpBqriQkV6Zi4lq9rL39bElJMG+KCsmaZ100XLWsXlKdhfxeWE5esXfkI+rpRXI86LHFyjXp2ZooqLIYob8Rymww1WAPy150XL6zx1lgUT8brZy8bQdOaJQbSW7FkQQ5QGMPh9bp5FOEY606jNZoucYjV3DsP41xUZSw1lX4YV27xuIuMMvDlHDw8HBhNsOj8C39ZTwq3qH0nUKTlJmJMuoJPY+Oi9EPCOkn6gYuhWdRRdCbMSvDRFSuUV3x+Pja4zurHxSw45raQWgdUn8YiorDXEJb+FmsQpX0I+XF/bZ9QerBPlFgsMxT3Rzj5+Bg25d2ixmMVx/D5JP9prD4rkytg+VyD/V/RWNyElW/LNEssa9l0KJTBUCp2u7R4ASvsMrO4lXS7btFO85K03PYOdcJqXGJT3Yk1IlkH2C51yye6YyUW8Sn9m7C6iGSA0fVM9EUfLORJW//NTVi+ImHoZdlAeCxfiHUzlomVHrKIxa2c7EqS+50KL7ObsKSeR1GusFoULff7RA0PMrtvJs4675L1GRb1W0420HAbfvp+5xPRVuZUDdZwUV8u095p5Yd9Kz9hN/RWnygyLPUrrrpJKyi6VOX1TwY2hBexxPBxrGKddhexNMoi9McX14IUR0mEWF5i4deUfz4jqEvi6vwaAnwOAGjlFtG1S2ojVlxdqP+HkCc0fZNeWtyS41IGSZc+tyNo1JyD6Myypqh53XFRnZstFJpmGRs1Aj+sqW1uzNk4GSE+4tM3E0kSsXnde3Xr3NU67WZuTX8H1ebH2UB9387KtiCgJFJ1K1UhGVjKy4ubRxEKwwN1/+2jPqggBigKtbuRqriXU9qK4khuxCKlp0Et/+fCm9piFioQvqrwG5vCj/vEJcsb9EWsG8UF5Z3e8uNHcUlNhFhXKP9VQppgvKvaqGYoY1lxuUi+t6t/gFCxcN3Vo7trqBInG9viG4PlwhvnQpupvuNKxyxjTT3rtrbjYNN9Gphi6StD6KzGRmw5FNg2J3ntELuaKlQkNe9hWXHBB5YcUHlXqPr7q7j+Wu1WX8X3F6p3awPfqHn8E9V7lZQ6a4fSQ0+v4CpRvVN32iWdE2EFKdjfuaYWnTWXqsKK7QVTJxSOecu/cM211mSRWZC1Nc0spSLNk0I0Yue5phE0uNoKrqsAfyBNOifC3fqZ69Tilk16lVXKJ4m2Cqwp1TRbehabKKg4s/6gSQuc5+rSlBqt6S6YpWWjDp4Mp4lyU2eE1aVnRfhZRNqOvtFdYCcim1BYomR93Fo/Ue45da7EzNp4jZ0rNcvX19jPwcYONE8Ff+g/Inm+0b4iAzO275b0AopxGjynpvcl1SksyGsauLc3krVNaEvr6qz8OJuHsD+cUXWLm1Q1AvZ51hiQpz/oN32iC9RUTvUkeZTr2iZh0TYJq7ZJmfudHicbtFHGvR9BOK42o+rzMaxtMoWsjKc5bDs5iLcoz9tMWJ4hq27JpXmXMI47J/BWYXrOBZtNppUNzGGZylKdJ/uF+IcNzBRY2io8N7p7pz6aEuY3laxe075Ztnu/xob6+UYdafbbA+rbvR2VwRxsPuFAOXNinO6J5/I8iACl+bJMbKdpobo5Poxg6CefKugjVhPLJyxci7jAkhB71xf6tdtKUXuUwKRX41kCdIk1eP+0wAonCcTe9Zxrt8Hj6OAFWGu7DFsPgyVLsYQvh0mxKBswE27Ktd92AofRW4jjdToHowyQJ1gu3LB6lWCF3fr8lAo+OnyynxM6ShiBfVnGtMEh9yey5/OhHg7LqpadqCrBctzL00Ysl2m7HsSBZz3MYzV+IHghVqYMEqzBitMqV4IFXSkZEw4EGQ5i3Jr0mtq8R4LlmsIJDuuZWHjT40DyknNsLFbvtL71HvQQqyYSughrcDjj5+9gCe/lhP38KawwKf30+C0sFY/XwXFN+j0szsfzYsJBMXQgJNrxbx4596MH9P3ocYbu8Mf+9w5/3Dwqk3/3qEy3JIP1waJ/3ib9/3TYfwHWPwIMAII5sDSNttNxAAAAAElFTkSuQmCC\"/>\n",
    "\n",
    "```\n",
    "WUMYMDSR\n",
    "ZQRKJPIZ\n",
    "DCYMSLWZ\n",
    "IXUGYZBB\n",
    "SRWUMYMD\n",
    "JKRQZZIP\n",
    "OWAHBGVG\n",
    "MYMUWRSD\n",
    "```\n",
    "\n",
    "Koliko različnih ogrlic ima? Osem? Ne. Peti dan je nosila isto ogrlico kot prvi, le malo drugače je bila zasukana. Pa tudi zadnji dan je nosila isto ogrlico, le da ni samo zasukana temveč tudi prezrcaljena (prvi dan si jo je nataknila čez glavo, osmi pa čez noge).\n",
    "\n",
    "Napiši program, ki za podano datoteko pove, koliko različnih ogrlic vsebuje.\n",
    "\n",
    "Vsebino datoteke boste najlažje prebrali z\n",
    "\n",
    "```python\n",
    "ogrlice = list(map(str.strip, open(\"ogrlice1000.txt\")))\n",
    "```\n",
    "\n",
    "`ogrlice1000.txt` seveda zamenjate z imenom datoteke, ki jo želite brati.\n",
    "\n",
    "\n",
    "## Za matematike ali programerje\n",
    "\n",
    "Recimo, da ima osumljenka 1000 različnih ogrlic. Opazujemo jo 1000 dni. Koliko različnih ogrlic bomo videli?\n",
    "\n",
    "Odgovor je seveda odvisen od sreče. Morda (a ne prav verjetno) vseh 1000, morda (a enako neverjetno) samo eno. Kakšno pa je *pričakovano število različnih ogrlic?? Če bi ta eksperiment velikokrat ponovili (večkrat opazujemo isto osumljenko za 1000 dni in preverimo, koliko različnih ogrlic je pokazala): koliko ogrlic bi videli v poprečju?\n",
    "\n",
    "To se da izračunati ali simulirati."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Kako je sestavljena naloga\n",
    "\n",
    "Če koga zanima je tole program, ki je sestavil datoteki z ogrlicami."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import string\n",
    "\n",
    "def necklace(n):\n",
    "    \"\"\"Sestavi ogrlico, dolgo `n` znakov\"\"\"\n",
    "    return \"\".join(random.choice(string.ascii_uppercase) for _ in range(n))\n",
    "\n",
    "def scramble(necklace):\n",
    "    \"\"\"Obrni ogrlico za naključno število znakov; zrcali z verjetnostjo 50%\"\"\"\n",
    "    shift = random.randint(1, len(necklace) - 2)\n",
    "    return (necklace[shift:] + necklace[:shift])[::random.choice([-1, 1])]\n",
    "\n",
    "def taskset(n, m, p, r):\n",
    "    \"\"\"\n",
    "    Sestavi m + p + r ogrlic dolžine n, od tega m unikatnih.\n",
    "    `r` je ogrlic ponovljenih trikrat, p - r pa dvakrat.\n",
    "    \n",
    "    Ogrlice so dovolj dolge, da ni verjetno, da bi slučajno dobili dve enaki.\n",
    "    \"\"\"\n",
    "    necklaces = [necklace(n) for _ in range(m)]\n",
    "    necklaces += map(scramble, necklaces[:p])\n",
    "    necklaces += map(scramble, necklaces[:r])\n",
    "    random.shuffle(necklaces)\n",
    "    return necklaces\n",
    "    \n",
    "# Testne datoteke\n",
    "for n, m, p, r in ((50, 15, 5, 0), (50, 975, 20, 5)):\n",
    "    open(f\"ogrlice{m + p + r}.txt\", \"wt\").write(\"\\n\".join(taskset(n, m, p, r)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rešitev\n",
    "\n",
    "Preberimo podatke, da bodo na voljo za poganjanje spodnjih koščkov kode. Poleg tega si pripravimo še nekaj ogrlic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "ogrlice = list(map(str.strip, open(\"ogrlice1000.txt\")))\n",
    "\n",
    "ogrlica1 = \"ABCDEF\"\n",
    "ogrlica1b = \"CDEFAB\"\n",
    "ogrlica1c = \"CBAFED\"\n",
    "\n",
    "ogrlica2 = \"ACBDFE\"  # ni enaka gornjim\n",
    "\n",
    "ogrlica3 = \"ABCXYZ\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Naloga ima dva problema: kako primerjati dve ogrlici in kako organizirati primerjanje, da ne bo potrebno primerjati vsake z vsako. Sam sem imel v mislih dve strategiji (vendar je ena prepočasna), v študentskih rešitvah pa sem videl še dve (vendar je ena napačna).\n",
    "\n",
    "## Primerjanja parov\n",
    "\n",
    "### Primerjanje z urejanjem\n",
    "\n",
    "Napačna ideja je takšna: ogrlici `o1` in `o2` sta enaki, če velja `sorted(o1) == sorted(o2)`. To bi bilo res, če bi osumljenka občasno razdrla kakšno ogrlico in spremenila vrstni red kroglic. Gornji pogoj namreč preverja le, ali sta ogrlici sestavljeni iz enakih kroglic, ne glede na vrstni red. Problem je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(ogrlica1) == sorted(ogrlica2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Po drugi strani to *navadno* deluje, če so ogrlice dovolj dolge in je število različnih kroglic dovolj veliko. Iz 26 črk angleške abecede lahko sestavimo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "56061846576641933068511861128435847024473459936647893758520097689829376"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "26 ** 50"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ogrlic dolžine 50, torej je verjetnost, da bosta dve vsebovali enake črke enaka"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.4901161193847656e-08"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 ** -26"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Če hočemo biti res prepričani, pa lahko rešimo nalogo tako, da najprej primerjamo urejene ogrlice, če zalotimo dve z enakimi kroglicami, pa s kako počasnejšo, a pravilno metodo preverimo, ali sta tudi res enaki. Nekatere študentske rešitve so bile v resnici narejene tako. Lepo.\n",
    "\n",
    "### Primerjanje z vrtenjem\n",
    "\n",
    "To je počasna rešitev, ki sem jo imel v mislih. Da preverimo, ali sta dve ogrlici enaki, pustimo eno pri miru, drugo pa vrtimo in opazujemo, ali je kateri od obratov enak."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nalogo je najpreprosteje rešiti tako, da pripravimo \"normirano\" obliko ogrlice. Ogrlico dolžine $n$ je možno opisati na $2n$ načinov (malo verjetno je, da bi bila dva obrata slučajno enaka). Med vsemi $2n$ načini poiščemo tistega, ki je prvi po abecedi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n",
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def same(o1, o2):\n",
    "    for o2 in (o2, o2[::-1]):  # o2 bo taka kot je in še obrnjena\n",
    "        for i in range(len(o2)):  # range(len(o2)) ... ker res potrebujem samo indekse, ne elementov :)\n",
    "            if o2[i:] + o2[:i] == o1:\n",
    "                return True\n",
    "    return False\n",
    "\n",
    "for o2 in [ogrlica1, ogrlica1b, ogrlica1c, ogrlica2, ogrlica3]:\n",
    "    print(same(ogrlica1, o2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zadnji dve sta različni in to je prav. Ni pa hitro. Če je $n$ dolžina ogrlice, poskusimo n obratov ($\\times 2$, a pustimo do) in v vsakem obratu na novo sestavimo ogrlico z $n$ kroglicami, torej je čas, potreben za primerjavo dveh ogrlic, sorazmeren $n^2$ (čas za primerjavo z urejanjem je bil sorazmeren hitrosti urejanja $n$ elementov, ta pa je $n\\log n$, kar je precej manj). A to še ni tako hudo, bolj je nerodno, da to delamo za vsak par ogrlic -- razen, če se znajdemo kako drugače. Več o tem kasneje.\n",
    "\n",
    "### Primerjanje s podvajanjem\n",
    "\n",
    "Tole ni tako neobičajen trik, vendar nanj nisem pomislil. Pač pa je nanj pomislilo več študentov. Če ogrlico podvojimo, se v njej pojavijo tudi vsi njeni obrati."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n",
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def same(o1, o2):\n",
    "    return o1 in o2 * 2 or o1 in o2[::-1] * 2\n",
    "\n",
    "for o2 in [ogrlica1, ogrlica1b, ogrlica1c, ogrlica2, ogrlica3]:\n",
    "    print(same(ogrlica1, o2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kako hitra pa je ta reč? Odvisna je od tega, kako deluje `in`. Naivna izvedba bi imela kvadratno časovno zahtevnost, tako kot gornje obračanje; v praksi bi seveda delovala bistveno hitreje, saj imamo 26 različnih znakov. Če koga zanima, pa je to primeren trenutek za reklamo za tri zele zanimive algoritme za iskanje podnizov: [Knuth-Morris-Prattov](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm), [Boyer-Moorov](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm#Performance) in [Rabin-Karpov](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm). Kaj od tega uporablja Python? V [kodi funkcije za iskanje](https://github.com/python/cpython/blob/master/Objects/stringlib/fastsearch.h) piše, da je to `a mix between boyer-moore and horspool, with a few more bells and whistles on the top`, zraven pa je še [povezava na detajle](http://effbot.org/zone/stringlib.htm).\n",
    "\n",
    "Karkoli: tole je res hitro, težava metode pa je, da tudi to lahko uporabljamo le tako, da kličemo gornjo funkcijo `same` za vsak par ogrlic (razen, morda, za tiste, ki smo jih že izločili kot duplikate).\n",
    "\n",
    "### Normalizacija\n",
    "\n",
    "Ideja, ki sem jo imel v mislih jaz, pa je taka. Gremo čez vse ogrlice in vsako preobrnem oz. prezrcalimo v njeno \"normalizirano\" obliko. Ogrlico dolžine $n$ je možno opisati na $2n$ načinov. Med vsemi $2n$ načini poiščemo tistega, ki je prvi po abecedi in opis ogrlice zamenjamo z njim."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def normalize(necklace):\n",
    "    \"\"\"Vrne opis ogrlice, ki je prvi po abecedi.\"\"\"\n",
    "    shifted = []\n",
    "    for shift in range(len(necklace)):\n",
    "        shneck = necklace[shift:] + necklace[:shift]\n",
    "        shifted += [shneck, shneck[::-1]]\n",
    "    return min(shifted)\n",
    "\n",
    "def same(o1, o2):\n",
    "    return o1 == o2  # predpostavlja, da sta ogrlici v normalizirani obliki"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Normalizacija zahteva kvadraten čas, vendar je dovolj, da jo opravimo le enkrat za vsako ogrlico. Primerjanje pa je potem trivialno, saj so vse enake ogrlice tudi zapisane enako. Predvsem pa nam po tem morda niti ne bo potrebno primerjati - vsaj ne eksplicitno.\n",
    "\n",
    "Mimogrede se lahko spomnimo zanimivejšega (in drobno malenkost hitrejšega) načina vrtenja. Inspirira nas namreč podvojevanje seznama. V gornji funkciji `necklace[shift:] + necklace[:shift]` sestavi dva seznama (z rezanjem) in ju sešteje. Namesto tega lahko sestavimo dvojni seznam in režemo znotraj njega. Tako imamo namesto dveh rezin in enega seštevanja le eno rezino."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def normalize(necklace):\n",
    "    \"\"\"Vrne opis ogrlice, ki je prvi po abecedi.\"\"\"\n",
    "    shifted = []\n",
    "    n = len(necklace)\n",
    "    necklace *= 2  # podvojimo seznam!\n",
    "    for shift in range(n):\n",
    "        shneck = necklace[shift:shift + n]\n",
    "        shifted += [shneck, shneck[::-1]]\n",
    "    return min(shifted)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Štetje unikatov\n",
    "\n",
    "### Groba sila\n",
    "\n",
    "Najpreprostejši način iskanja duplikatov je, da gremo čez seznam, vsako ogrlico primerjamo z vsemi, ki smo jih videli doslej in če je ni med njimi, smo našli nov unikat. Celotna rešitev (skupaj z učinkovito funkcijo `same`) bi bila potem takšna:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "975\n"
     ]
    }
   ],
   "source": [
    "def same(o1, o2):\n",
    "    return o1 in o2 * 2 or o1 in o2[::-1] * 2\n",
    "\n",
    "\n",
    "unikatov = 0\n",
    "for i, o1 in enumerate(ogrlice):\n",
    "    for o2 in ogrlice[:i]:\n",
    "        if same(o1, o2):\n",
    "            break\n",
    "    else:\n",
    "        unikatov += 1\n",
    "\n",
    "print(unikatov)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Seznami (ali množice) nenormalnih ogrlic\n",
    "\n",
    "Nekateri so se izognili notranji zanki (in, v bistvu, funkciji `same`) tako, da so sestavljali seznam že znanih ogrlic, ki ni vseboval le ogrlic v podani obliki temveč tudi vse obrate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "975\n"
     ]
    }
   ],
   "source": [
    "unikatov = 0\n",
    "videne = []\n",
    "\n",
    "for o1 in ogrlice:\n",
    "    if o1 not in videne:\n",
    "        unikatov += 1\n",
    "        for o1 in (o1, o1[::-1]):\n",
    "            for i in range(len(o1)):\n",
    "                videne.append(o1[i:] + o1[:i])\n",
    "\n",
    "print(unikatov)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To celo deluje in celo dokaj hitro - če pomislimo, da ima vsaka ogrlica 100 obratov (vključno z zrcaljenji), tako da imamo na koncu seznam (skoraj) 1000*100 = 100000 ogrlic in za vsako novo ogrlico mora Python preveriti, ali je kje v tem seznamu.\n",
    "\n",
    "Gornji program se izvaja sekundo ali dve. Čez kako uro pa bomo izvedeli, da je program opazno hitrejši, če zamenjamo seznam z množico - le `[]` zamenjamo s `set()` in `append` z `add`, vse ostalo ostane enako."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "975\n"
     ]
    }
   ],
   "source": [
    "unikatov = 0\n",
    "videne = set()\n",
    "\n",
    "for o1 in ogrlice:\n",
    "    if o1 not in videne:\n",
    "        unikatov += 1\n",
    "        for o1 in (o1, o1[::-1]):\n",
    "            for i in range(len(o1)):\n",
    "                videne.add(o1[i:] + o1[:i])\n",
    "\n",
    "print(unikatov)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Seznami (ali množice) normalnih ogrlic\n",
    "\n",
    "Zdaj pa še rešitev, ki sem jo imel v mislih: podobna je gornji, le da v množico ne damo vseh ogrlic temveč le ogrlico v obratu, ki je prvi po abecedi. Program bomo torej napisali tako, da bo najprej zamenjal seznam ogrlic s seznamom normaliziranih ogrlic, potem pa bo podoben gornjemu programu, le da ne bo vrtel ogrlic med dodajanjem in, predvsem, ne bo dodajal vseh obratov. Ker pomnilnik."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "975\n"
     ]
    }
   ],
   "source": [
    "def normalize(necklace):\n",
    "    \"\"\"Vrne opis ogrlice, ki je prvi po abecedi.\"\"\"\n",
    "    shifted = []\n",
    "    for shift in range(len(necklace)):\n",
    "        shneck = necklace[shift:] + necklace[:shift]\n",
    "        shifted += [shneck, shneck[::-1]]\n",
    "    return min(shifted)\n",
    "\n",
    "def all_normalized(necklaces):\n",
    "    \"\"\"Prejme seznam ogrlic in vrne seznam z normaliziranimi opisi.\"\"\"\n",
    "    normalized = []\n",
    "    for necklace in necklaces:\n",
    "        normalized.append(normalize(necklace))\n",
    "    return normalized\n",
    "\n",
    "def unique(s):\n",
    "    \"\"\"Prejme seznam in vrne seznam unikatnih elementov.\"\"\"\n",
    "    u = []\n",
    "    for x in s:\n",
    "        if x not in u:\n",
    "            u.append(x)\n",
    "    return u\n",
    "\n",
    "print(len(unique(all_normalized(ogrlice))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Od prihodnjega tedna bomo znali vse to opisati krajše."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "975\n"
     ]
    }
   ],
   "source": [
    "def normalize(necklace):\n",
    "    \"\"\"Vrne opis ogrlice, ki je prvi po abecedi.\"\"\"\n",
    "    shifted = [necklace[shift:] + necklace[:shift] for shift in range(len(necklace))]\n",
    "    shifted += [necklace[::-1] for necklace in shifted]\n",
    "    return min(shifted)\n",
    "\n",
    "def all_normalized(necklaces):\n",
    "    \"\"\"Prejme seznam ogrlic in vrne seznam z normaliziranimi opisi.\"\"\"\n",
    "    return [normalize(necklace) for necklace in necklaces]\n",
    "\n",
    "def unique(s):\n",
    "    \"\"\"Prejme seznam in vrne seznam unikatnih elementov.\"\"\"\n",
    "    u = []\n",
    "    for x in s:\n",
    "        if x not in u:\n",
    "            u.append(x)\n",
    "    return u\n",
    "\n",
    "print(len(unique(all_normalized(ogrlice))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Že čez kako uro bomo izvedeli, da lahko `unique` naredimo tudi tako (le da tule vrne množico, kar pa je vseeno)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "975\n"
     ]
    }
   ],
   "source": [
    "def unique(s):\n",
    "    return set(s)\n",
    "\n",
    "print(len(unique(all_normalized(ogrlice))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tako kratka funkcija seveda ni vredna funkcije. Celotna rešitev izziva, kot jo bomo pisali od prihodnjega tedna naprej, bo zato kar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "975\n"
     ]
    }
   ],
   "source": [
    "def normalize(necklace):\n",
    "    \"\"\"Vrne opis ogrlice, ki je prvi po abecedi.\"\"\"\n",
    "    shifted = [necklace[shift:] + necklace[:shift] for shift in range(len(necklace))]\n",
    "    shifted += [necklace[::-1] for necklace in shifted]\n",
    "    return min(shifted)\n",
    "\n",
    "print(len({normalize(necklace) for necklace in ogrlice}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zadnjo vrstico lahko, če vam je bolj všeč, pišete tudi kot:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "975\n"
     ]
    }
   ],
   "source": [
    "print(len(set(map(normalize, ogrlice))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Koliko različnih ogrlic vidimo?\n",
    "\n",
    "Poleg čisto lepega algoritmičnega ozadja je za nalogo tudi nekaj matematike, verjetnosti, statistike. Vprašanje, ki bi si ga lahko zastavili, je tole: v 1000 dneh smo damo videli s 632 različnimi ogrlicami. Koliko različnih ogrlic ima potem (najbrž) v resnici?\n",
    "\n",
    "Vendar si nismo zastavili tega vprašanja, temveč obratnega. Vemo, da ima 1000 ogrlic, opazovali smo jo 1000 dni in vprašanje je, koliko različnih ogrlic bomo (najbrž) opazili.\n",
    "\n",
    "### Simulacija\n",
    "\n",
    "Za odgovor na vprašanje ni potrebno sestavljati ogrlic. Dovolj je, da si predstavljamo, da imamo 1000 oštevilčenih ogrlic in namesto ogrlic izbiramo kar številke med 1 in 1000 ter jih dajemo v seznam, vendar vsako številko dodamo le, če je unikatna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "def razlicnih(n):\n",
    "    ogrlice = []\n",
    "    for i in range(n):  # n dni\n",
    "        ogrlica = randint(1, n)\n",
    "        if ogrlica not in ogrlice:\n",
    "            ogrlice.append(ogrlica)\n",
    "    return len(ogrlice)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "643"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "razlicnih(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Isto lahko delamo tudi z `numpy`-jem, če ga že ravno poznamo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "626"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def razlicnih(n):\n",
    "    return len(np.unique(np.random.randint(1, n, n)))\n",
    "\n",
    "razlicnih(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ali pa zamenjamo sezname z množicami. Poleg tega lahko uporabimo še, kar se bomo pravzaprav učili prihodnji teden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "636"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def razlicnih(n):\n",
    "    return len({randint(1, 1000) for _ in range(1000)})\n",
    "\n",
    "razlicnih(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kakorkoli že definiramo funkcijo: vsakič vrne drugačno vrednost; pokličemo jo (recimo) desettisočkrat in iračunamo poprečje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "632.3354"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v = 0\n",
    "for i in range(10000):  # 10000-krat ponovimo poskus\n",
    "    v += razlicnih(1000)\n",
    "\n",
    "v / 10000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Matematična rešitev\n",
    "\n",
    "Imejmo `n` ogrlic. Kakšna je verjetnost, da posamično (recimo kar: prvo) izberemo vsaj enkrat? Verjetnost, da jo izberemo v prvem poskusu je $\\frac{1}{n}$, verjetnost, da jo v drugem prav tako ... A s tem ne bomo prišli daleč. Lažje je izračunati, kakšna je verjetnost, da je *ne izberemo* v nobenem poskusu. Verjetnost, da je ne izberemo v prvem, je $1 - \\frac{1}{n}$, verjetnost, da je ne v drugem, prav tako ... in tako naprej. Verjetnost, da je ne izberemo v nobenem od $n$ poskusov, je $\\left(1 - \\frac{1}{n}\\right)^n$. Torej je verjetnost, da jo izberemo v vsaj enem, enaka $1 - \\left(1 - \\frac{1}{n}\\right)^n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6323045752290363"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 1000\n",
    "1 - (1 - 1 / n) ** n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Imamo torej $n$ ogrlic in za vsako je verjetnost, da jo izberemo, enaka $1 - \\left(1 - \\frac{1}{n}\\right)^n$. Skupaj torej izberemo $n \\left(1 - \\left(1 - \\frac{1}{n}\\right)^n\\right)$ ogrlic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "632.3045752290362"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n * (1 - (1 - 1 / n) ** n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Spomnimo se lahko še, da velja $e = \\lim\\limits_{x \\to 0 } {\\left( {1 + x} \\right)^{\\frac{1}{x}}}$. Zamenjamo $x = -\\frac{1}{n}$ in imamo dobimo $ \\lim\\limits_{n \\to \\infty } {\\left( {1 - \\frac{1}{n}} \\right)^n} = e^{-1}$. Ko je $n$ primerno velik, bo verjetnost, da izberemo ogrlico, enaka $1 - e^{-1}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6321205588285577"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from math import exp\n",
    "1 - exp(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pričakovano število izbranih ogrlic je zato $n\\left(1 - e^{-1}\\right)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "632.1205588285577"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n * (1 - exp(-1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Takšen način izbiranja se pogosto uporablja v statistiki (imenuje se [bootstrapping](https://en.wikipedia.org/wiki/Bootstrapping_(statistics))) in številka 0.632 je vsakemu, ki se ukvarja s statistiko ali umetno inteligenco dobro znana."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}