Solución del problema 20

Ejercicio20.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solución al ejercicio 20 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En este Jupyter Notebook se presenta la solución al ejercicio 20 de [este taller](https://docs.google.com/a/unal.edu.co/viewer?a=v&pid=sites&srcid=dW5hbC5lZHUuY298Y2FtaWxvLWFyaWFzLWFiYWR8Z3g6NGU0ZTdkNDZkMDRhMjA2NQ)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algoritmo que encuentra las particiones de un número "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jerome Kelleher presenta en [este blog](http://jeromekelleher.net/tag/integer-partitions.html) un algoritmo rápido para encontrar las particiones de un número:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def rule_asc(n):\n",
    "    a = [0 for i in range(n + 1)]\n",
    "    k = 1\n",
    "    a[1] = n\n",
    "    while k != 0:\n",
    "        x = a[k - 1] + 1\n",
    "        y = a[k] - 1\n",
    "        k -= 1\n",
    "        while x <= y:\n",
    "            a[k] = x\n",
    "            y -= x\n",
    "            k += 1\n",
    "        a[k] = x + y\n",
    "        yield a[:k + 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Encontrando el máximo orden de $S_{17}$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sabemos que el orden de un elemento se maximiza cuando el mínimo común múltiplo de las longitudes de sus ciclos es máxima. Es decir, podemos encontrar el máximo orden al encontrar la partición de $17$ que maximiza el mínimo común múltiplo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Usamos la función `gcm` de la librería estandar de matemáticas y usamos la función `reduce` para poder aplicarla sucesivamente a elementos en una lista."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "210 [2, 3, 5, 7]\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "from math import gcd\n",
    "\n",
    "# Definimos el mínimo común múltiplo aprovechando que a*b = [a,b](a,b).\n",
    "def lcm(a,b):\n",
    "    return a*b//gcd(a,b)\n",
    "\n",
    "# Extendemos esta función a listas usando reduce.\n",
    "def lcm_for_lists(_list):\n",
    "    return reduce(lcm, _list)\n",
    "\n",
    "# Sacamos las particiones de 17\n",
    "partitions_of_17 = list(rule_asc(17))\n",
    "\n",
    "# Encontramos el mcm para todas las particiones de 17\n",
    "list_of_lcm = [lcm_for_lists(partition) for partition in partitions_of_17]\n",
    "\n",
    "# Conseguimos el índice en donde aparece el máximo\n",
    "index_of_max_lcm = list_of_lcm.index(max(list_of_lcm))\n",
    "\n",
    "# Imprimimos la partición y el máximo de la lista list_of_lcm\n",
    "print(list_of_lcm[index_of_max_lcm], partitions_of_17[index_of_max_lcm])"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}