Laboratorio 1 punto 6

Lab1-6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Laboratorio-1 Punto 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Programas para ejecutar el algoritmo de ordenamiento  InsertionSort sobre todas las permutaciones:\n",
    "\n",
    "* Generadas con:\n",
    "    *  **Itertools.permutations** y determinar hasta que valor puede generar las permutaciones en memoria.\n",
    "    * Usando el código de Daniel Jimenez para generar las permutaciones sobre un unico arreglo\n",
    "    * Muestra aleatoria de permutaciones \n",
    "    \n",
    "Se debe generar el numero promedio y la distribución del numero de instrucciones ,comparaciones y intercambios que se requieren para ordenar.\n",
    "\n",
    "Algoritmos para Basarse:\n",
    "* [InsertSortTimePlot](http://disi.unal.edu.co/~algorithms/applets/InsertSortTimePlot/)\n",
    "* [insertionsort.py](http://disi.unal.edu.co/~algorithms/python/insertionsort.py)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Theoretical best time, 46\n",
      "Theoretical worst time,181.0\n",
      "Theoretical average time,113.5\n",
      "Experimenal best time, 46\n",
      "Experimenal worst time,181\n",
      "Experimenal average time,113\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "    Generacion de Permutaciones con codigo de :\n",
    "    http://disi.unal.edu.co/~algorithms/python/insertionsort.py\n",
    "    \n",
    "'''\n",
    "\n",
    "import random\n",
    "import itertools\n",
    "\n",
    "def randomPerm(n):\n",
    "    v=[]\n",
    "    for i in range(n):\n",
    "        v.append(i+1)\n",
    "    for i in range(len(v)-1):\n",
    "        j = random.randint(i, len(v)-1)\n",
    "        aux = v[i]\n",
    "        v[i] = v[j]\n",
    "        v[j] = aux\n",
    "    return v\n",
    "\n",
    "def isortSteps(a):\n",
    "    v = []\n",
    "    for i in range(len(a)):\n",
    "        v.append(a[i])\n",
    "        \n",
    "    steps = 0\n",
    "    for i in range(1,len(v)):\n",
    "        x = v[i]\n",
    "        j = i-1\n",
    "        while (j > -1) and (v[j] > x):\n",
    "            v[j+1] = v[j]\n",
    "            j = j -1\n",
    "            steps += 3\n",
    "        steps += 1\n",
    "        v[j+1] = x\n",
    "        steps += 4\n",
    "    steps += 1\n",
    "    return steps\n",
    "\n",
    "#Temaño del arreglo\n",
    "n = 10\n",
    "runs = 0\n",
    "\n",
    "array = []\n",
    "\n",
    "array = randomPerm(n)\n",
    "sum = 0\n",
    "\n",
    "min = n**3\n",
    "max = 0\n",
    "\n",
    "#generacion y conteo pasos en cada permutacion\n",
    "for i in itertools.permutations(array):\n",
    "    t = isortSteps(i)\n",
    "    #print(t, end=' ')\n",
    "    if t < min :\n",
    "       min = t\n",
    "    if t > max :\n",
    "       max = t\n",
    "    sum  += t\n",
    "    runs += 1\n",
    "print ('Theoretical best time, ' + str(5*n - 4))\n",
    "print ('Theoretical worst time,' + str((3.0/2.0)*n**2 + (7.0/2.0)*n - 4))\n",
    "print ('Theoretical average time,' + str((3.0/4.0)*n**2 + (17.0/4.0)*n - 4))\n",
    "print ('Experimenal best time, ' + str(min))\n",
    "print ('Experimenal worst time,' + str(max))\n",
    "print ('Experimenal average time,' + str(sum/runs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Theoretical best time, 46\n",
      "Theoretical worst time,181.0\n",
      "Theoretical average time,113.5\n",
      "Experimenal best time, 67\n",
      "Experimenal worst time,163\n",
      "Experimenal average time,113\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "    Generacion de Permutaciones con codigo de:\n",
    "    http://disi.unal.edu.co/~algorithms/python/insertionsort.py\n",
    "    con una muestra aleatoria de permutaciones\n",
    "    \n",
    "'''\n",
    "import random\n",
    "def randomPerm(n):\n",
    "    v=[]\n",
    "    for i in range(n):\n",
    "        v.append(i+1)\n",
    "    for i in range(len(v)-1):\n",
    "        j = random.randint(i, len(v)-1)\n",
    "        aux = v[i]\n",
    "        v[i] = v[j]\n",
    "        v[j] = aux\n",
    "    return v\n",
    "\n",
    "\n",
    "def isortSteps(a):\n",
    "    v = []\n",
    "    for i in range(len(a)):\n",
    "        v.append(a[i])\n",
    "        \n",
    "    steps = 0\n",
    "    for i in range(1,len(v)):\n",
    "        x = v[i]\n",
    "        j = i-1\n",
    "        while (j > -1) and (v[j] > x):\n",
    "            v[j+1] = v[j]\n",
    "            j = j -1\n",
    "            steps = steps + 3\n",
    "        steps = steps + 1\n",
    "        v[j+1] = x\n",
    "        steps = steps + 4\n",
    "    steps = steps + 1\n",
    "    return steps\n",
    "\n",
    "\n",
    "n = 10\n",
    "\n",
    "num = 900\n",
    "#cantidad de muestra de permutaciones seleccionadas\n",
    "suma = 0\n",
    "best = n ** 3\n",
    "worst = 0\n",
    "for i in range(num):\n",
    "    t = isortSteps(randomPerm(n))\n",
    "    #print(t, end=' ')\n",
    "    if t < best:\n",
    "        best = t\n",
    "    if t > worst:\n",
    "        worst = t\n",
    "    suma = suma + t\n",
    "print ('Theoretical best time, ' + str(5*n - 4))\n",
    "print ('Theoretical worst time,' + str((3.0/2.0)*n**2 + (7.0/2.0)*n - 4))\n",
    "print ('Theoretical average time,' + str((3.0/4.0)*n**2 + (17.0/4.0)*n - 4))\n",
    "print ('Experimenal best time, ' + str(best))\n",
    "print ('Experimenal worst time,' + str(worst))\n",
    "print ('Experimenal average time,' + str(suma/num))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Theoretical best time, 36\n",
      "Theoretical worst time,120.0\n",
      "Theoretical average time,78.0\n",
      "Experimenal best time, 8\n",
      "Experimenal worst time,5764801\n",
      "Experimenal average time,78\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "    Generación de Permutaciones mediante el codigo de Daniel Jimenez\n",
    "    \n",
    "'''\n",
    "#Generación de permutaciones recursivas codigo de daniel Jimenez\n",
    "def swap (a , b , c):\n",
    "    t = a[b]\n",
    "    a[b] = a[c]\n",
    "    a[c] = t\n",
    "\n",
    "\n",
    "def isortSteps(a):\n",
    "    v = []\n",
    "    for i in range(len(a)):\n",
    "        v.append(a[i])\n",
    "        \n",
    "    steps = 0\n",
    "    for i in range(1,len(v)):\n",
    "        x = v[i]\n",
    "        j = i-1\n",
    "        while (j > -1) and (v[j] > x):\n",
    "            v[j+1] = v[j]\n",
    "            j = j -1\n",
    "            steps += 3\n",
    "        steps += 1\n",
    "        v[j+1] = x\n",
    "        steps += 4\n",
    "    steps += 1\n",
    "    return steps\n",
    "\n",
    "def dJPerm(v , i , n , d , cases):\n",
    "    '''\n",
    "        d[] arreglo con las variables a mostrar\n",
    "        d[0] = npermut \n",
    "        d[1] = total\n",
    "\n",
    "    '''\n",
    "    \n",
    "    j = 0\n",
    "    k = 0\n",
    "    l = 0\n",
    "    \n",
    "\n",
    "    if i == n :\n",
    "        d[0] += 1\n",
    "        k = isortSteps(v)\n",
    "        d[1] += k\n",
    "        cases[k] += 1\n",
    "    else:\n",
    "        j=i\n",
    "        for j in range(n-1):\n",
    "            swap(v,i,j)\n",
    "            dJPerm(v,i+1,n,d,cases)\n",
    "            swap(v,i,j)\n",
    "    \n",
    "    \n",
    "    '''for i in range(n):\n",
    "        v.append(i+1)\n",
    "    for i in range(len(v)-1):\n",
    "        j = random.randint(i, len(v)-1)\n",
    "        aux = v[i]\n",
    "        v[i] = v[j]\n",
    "        v[j] = aux\n",
    "    return v'''\n",
    "v = []\n",
    "#definicion de n aleatorio \n",
    "n = 8\n",
    "k = 0\n",
    "d = []\n",
    "d.append(0)\n",
    "d.append(0)\n",
    "cases = []\n",
    "#LLena el arreglo con ceros para hacer la comprobacion \n",
    "for i in range(n):\n",
    "    v.append(i)\n",
    "for i in range(1001):\n",
    "    cases.append(i)\n",
    "dJPerm(v , 0 , n , d , cases)\n",
    "print ('Theoretical best time, ' + str(5*n - 4))\n",
    "print ('Theoretical worst time,' + str((3.0/2.0)*n**2 + (7.0/2.0)*n - 4))\n",
    "print ('Theoretical average time,' + str((3.0/4.0)*n**2 + (17.0/4.0)*n - 4))\n",
    "print ('Experimenal best time, ' + str(n))\n",
    "print ('Experimenal worst time,' + str(d[0]))\n",
    "print ('Experimenal average time,' + str(d[1]/d[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}