python_pd/03_collections/05_itertools.ipynb

{
 "metadata": {
  "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.9.0-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "source": [
    "# Модуль ```itertools```\n",
    "\n",
    "В Python уже реализовано много полезных итераторов. Все они собраны в модуле ```itertools``` стандартной библиотеке. Итераторы сгруппированы в три группы:\n",
    "- бесконечные итераторы;\n",
    "- комбинаторные итераторы;\n",
    "- другие полезные итераторы.\n",
    "\n",
    "## Бесконечные итераторы\n",
    "\n",
    "Бесконечные итераторы реализуют бесконечные действия и никогда не останавливаются. Их всего три:\n",
    "- ```count``` - порождает бесконечную числовую последовательность, аналог ```range```, только не имеет параметра ```stop```;\n",
    "- ```cycle``` - принимает последовательность в качестве аргумента и бесконечно зацикливает ее;\n",
    "- ```repeat``` - принимает элемент и повторяет его бесконечное число раз, может быть конечным, если передать в качестве второго аргумента количество повторений."
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "i = 'spam'\ni = 'spam'\ni = 'spam'\ni = 'spam'\n"
     ]
    }
   ],
   "source": [
    "from itertools import repeat\n",
    "\n",
    "for i in repeat('spam', 4):\n",
    "    print(f'{i = }')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "i = 's'\ni = 'p'\ni = 'a'\ni = 'm'\ni = 's'\ni = 'p'\n"
     ]
    }
   ],
   "source": [
    "from itertools import cycle\n",
    "\n",
    "k = 0\n",
    "for i in cycle('spam'):\n",
    "    if k > 5:\n",
    "        break\n",
    "    print(f'{i = }')\n",
    "    k += 1"
   ]
  },
  {
   "source": [
    "## Комбинаторика\n",
    "\n",
    "Довольно часто встречаются задачи перебора различных вариантов подпоследовательностей, основанных на нескольких других последовательностях. Например всех возможных последовательностей длиной 2, составленных из списка ```[1, 2, 3, 4]```. Для таких [комбинаторных задач](https://en.wikipedia.org/wiki/Enumerative_combinatorics), т.е. задач основанных на подсчете или построении и переборе конфигураций, реализован ряд итераторов, решающих классические задачи:\n",
    "- ```product``` вычисляет [декартово произведение](https://en.wikipedia.org/wiki/Cartesian_product) нескольких последовательностей;\n",
    "- ```permutations``` вычисляет все [размещения](https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n) на основе переданной последовательности, можно задать длину перестановки;\n",
    "- ```combinations``` вычисляет все [сочетания без повторений](https://en.wikipedia.org/wiki/Combination) на основе переданной последовательности, можно задать длину сочетания;\n",
    "- ```combinations_with_replacement``` вычисляет все [сочетания с повторениями](https://en.wikipedia.org/wiki/Combination) на основе переданной последовательности, можно задать длину сочетания;\n",
    "\n",
    "Итератор ```product``` отлично подходит для упрощения вложенных циклов. Например, необходимо перебрать все возможные варианты нескольких последовательностей: строки ```abc``` и списка ```[1, 2, 3, 4]```. Каждый набор параметров будет состоять из двух элементов - одного символа и одного числа. Всего таких наборов будет $3 \\cdot 4 = 12$ или ```len('abc') * len([1, 2, 3, 4])```. В этом случае можно воспользоваться двойным циклом. Но в этом случае будет образован дополнительный отступ, что вредит читаемости кода. Использование ```product``` позволит обойтись одним циклом и решить ту же задачу более коротко, сохранив читаемость на высоком уровне."
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "(a; 1)\n(a; 2)\n(a; 3)\n(a; 4)\n(b; 1)\n(b; 2)\n(b; 3)\n(b; 4)\n(c; 1)\n(c; 2)\n(c; 3)\n(c; 4)\n"
     ]
    }
   ],
   "source": [
    "s = 'abc'\n",
    "a = [1, 2, 3, 4]\n",
    "\n",
    "for i in s:\n",
    "    for j in a:\n",
    "        print(f'({i}; {j})')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "item = ('a', 1)\nitem = ('a', 2)\nitem = ('a', 3)\nitem = ('a', 4)\nitem = ('b', 1)\nitem = ('b', 2)\nitem = ('b', 3)\nitem = ('b', 4)\nitem = ('c', 1)\nitem = ('c', 2)\nitem = ('c', 3)\nitem = ('c', 4)\n"
     ]
    }
   ],
   "source": [
    "from itertools import product\n",
    "\n",
    "for item in product(s, a):\n",
    "    print(f'{item = }')"
   ]
  },
  {
   "source": [
    "Создать все возможные комбинации определенной длины на основе одной последовательности позволяет функция ```permutations```. На основе ```permutations``` можно сгенерировать все [перестановки](https://en.wikipedia.org/wiki/Permutation), не задавая длину."
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "item = (1, 2)\nitem = (1, 3)\nitem = (1, 4)\nitem = (2, 1)\nitem = (2, 3)\nitem = (2, 4)\nitem = (3, 1)\nitem = (3, 2)\nitem = (3, 4)\nitem = (4, 1)\nitem = (4, 2)\nitem = (4, 3)\n"
     ]
    }
   ],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "xs = [1, 2, 3, 4]\n",
    "\n",
    "# все размещения длиной 2 списка xs\n",
    "for item in permutations(xs, 2):\n",
    "    print(f'{item = }')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "item = (1, 2, 3)\nitem = (1, 3, 2)\nitem = (2, 1, 3)\nitem = (2, 3, 1)\nitem = (3, 1, 2)\nitem = (3, 2, 1)\n"
     ]
    }
   ],
   "source": [
    "xs = [1, 2, 3]\n",
    "\n",
    "# все размещения списка xs\n",
    "for item in permutations(xs):\n",
    "    print(f'{item = }')"
   ]
  },
  {
   "source": [
    "## Другие полезные итераторы\n",
    "\n",
    "Кроме вышеперечисленных функций есть и другие полезные итераторы. Вот некоторые из них:\n",
    "- ```chain``` и ```chain.fro_iterable``` - поочередно возвращает элементы коллекций;\n",
    "- ```compress``` - возвращает элементы коллекции в соответствии с маской;\n",
    "- ```groupby``` - группирует элементы коллекции;\n",
    "- остальные смотрите в [документации](https://docs.python.org/3/library/itertools.html).\n",
    "\n",
    "Итератор ```chain``` принимает произвольное количество коллекций и поочередно возвращает их элементы, как только одна коллекция заканчивается он переходит к следующей. Итератор ```chain.fro_iterable``` выполняет тоже действие только принимает один итерируемый объект, внутри которого находятся коллекции.\n",
    "\n",
    "Примером использования этих итераторов может служить \"расплющивание\" двумерной коллекции."
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "flattened_1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2]\nflattened_2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2]\n"
     ]
    }
   ],
   "source": [
    "from itertools import chain\n",
    "\n",
    "# дан список списков, его нужно превратить в одномерный список\n",
    "matrix = [\n",
    "    [1, 2, 3, 4], \n",
    "    [5, 6, 7, 8], \n",
    "    [9, 0, 1, 2],\n",
    "]\n",
    "\n",
    "# используем распаковку и функцию chain\n",
    "flattened_1 = list(chain(*matrix))\n",
    "# или сразу передаем в chain.from_iterable\n",
    "flattened_2 = list(chain.from_iterable(matrix))\n",
    "print(f'{flattened_1 = }')\n",
    "print(f'{flattened_2 = }')"
   ]
  },
  {
   "source": [
    "Функция ```groupby``` одна из самых полезных. Она позволяет сгруппировать коллекцию в порядке следования."
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1: [1, 1, 1], 3\n3: [3], 1\n2: [2], 1\n1: [1], 1\n3: [3], 1\n2: [2], 1\n1: [1, 1], 2\n"
     ]
    }
   ],
   "source": [
    "from itertools import groupby\n",
    "\n",
    "xs = [1, 1, 1, 3, 2, 1, 3, 2, 1, 1]\n",
    "\n",
    "# groupby возвращает элемент, по которому идет группировка, \n",
    "# затем список всех элементов, составляющих эту группу\n",
    "# все элементы в группе будут одинаковы\n",
    "for key, group in groupby(xs):\n",
    "    # группы тояже являются итераторами\n",
    "    group = list(group)\n",
    "    print(f'{key}: {group}, {len(group)}')"
   ]
  },
  {
   "source": [
    "На основе ```groupby``` легко реализовать функцию вычисления последовательности [\"Посмотри и скажи\"](https://en.wikipedia.org/wiki/Look-and-say_sequence)."
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "look_and_say(2) = ['11', '21']\nlook_and_say(5) = ['11', '21', '1211', '111221', '312211']\nlook_and_say(10) = ['11', '21', '1211', '111221', '312211', '13112221', '1113213211', '31131211131221', '13211311123113112211', '11131221133112132113212221']\n"
     ]
    }
   ],
   "source": [
    "def look_and_say(n):\n",
    "    res = []\n",
    "    for i in range(n):\n",
    "        if i == 0:\n",
    "            item = '1'\n",
    "        item = ''.join([str(len(list(group))) + key for key, group in groupby(item)])\n",
    "        res.append(item)\n",
    "    return res\n",
    "\n",
    "print(f'{look_and_say(2) = }')\n",
    "print(f'{look_and_say(5) = }')\n",
    "print(f'{look_and_say(10) = }')"
   ]
  },
  {
   "source": [
    "# Полезные ссылки\n",
    "\n",
    "- [Документация](https://docs.python.org/3/library/itertools.html)"
   ],
   "cell_type": "markdown",
   "metadata": {}
  }
 ]
}