{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyMRUC3+Avu7MZizeQIrC42U", "include_colab_link": true }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "metadata": { "id": "view-in-github", "colab_type": "text" }, "source": [ "\"Open" ] }, { "cell_type": "markdown", "source": [ "# Algoritmo Deep Moder Times explicado" ], "metadata": { "id": "wLGaiaeCuIBR" } }, { "cell_type": "code", "source": [ "# FUNCIONES\n", "def sa(a,b):\n", " if len(a) > 1: a[0],a[1] = a[1],a[0]\n", " return a,b\n", "def sb(a,b):\n", " if len(b) > 1: b[0],b[1] = b[1],b[0]\n", " return a,b\n", "def ss(a,b):\n", " sa(a,b)\n", " sb(a,b)\n", " return a,b\n", "def pa(a,b):\n", " if len(b) > 0:\n", " a.insert(0, b[0])\n", " b.pop(0)\n", " return a,b\n", "def pb(a,b):\n", " if len(a) > 0:\n", " b.insert(0, a[0])\n", " a.pop(0)\n", " return a,b\n", "def ra(a,b):\n", " if len(a) > 1: a.append(a.pop(0))\n", " return a,b\n", "def rb(a,b):\n", " if len(b) > 1: b.append(b.pop(0))\n", " return a,b\n", "def rr(a,b):\n", " ra(a,b)\n", " rb(a,b)\n", " return a,b\n", "def rra(a,b):\n", " if len(a) > 1: a.insert(0, a.pop())\n", " return a,b\n", "def rrb(a,b):\n", " if len(b) > 1: b.insert(0, b.pop())\n", " return a,b\n", "def rrr(a,b):\n", " rra(a,b)\n", " rrb(a,b)\n", " return a,b" ], "metadata": { "id": "NnOxqobnuRzl" }, "execution_count": 1, "outputs": [] }, { "cell_type": "code", "source": [ "# Generación de la pila A\n", "from random import sample, seed\n", "seed()\n", "\n", "def generaPilaA(n):\n", " return sample(range(1, n+1), n)" ], "metadata": { "id": "spca5pwXubSh" }, "execution_count": 2, "outputs": [] }, { "cell_type": "code", "source": [ "# Llevamos de la pila A hacia la pila B los elementos de la LIS\n", "def rotateLIS(lis):\n", " global a\n", " global b\n", " global contador\n", " for vlis in lis:\n", " if a.index(vlis) < len(a)/2: # movemos el número hacia la izquierda hasta que queda el primero de la pila A\n", " for i in range(a.index(vlis)):\n", " ra(a,b); contador += 1\n", " else:\n", " for i in range(len(a)- a.index(vlis)): # movemos el número hacia la drecha hasta que queda el primero de la pila A\n", " rra(a,b); contador += 1\n", " pb(a,b); contador += 1 # aqui bajo el numero de la pila A a la B, puesto que ahora ese número ya está el primero de la pila A" ], "metadata": { "id": "8QAC4tTou36V" }, "execution_count": 3, "outputs": [] }, { "cell_type": "code", "source": [ "# PASOS NECESARIOS PARA COLOCAR CADA ELEMENTO DE A EN SU SITIO EN B total = pasosA + pasosB\n", "\n", "def necesariosA(a, b): # array pasosA calcula los pasos necesarios para colocar cada elemento de A como el primero de su pila\n", " for i in a:\n", " if a.index(i) < len(a)/2:\n", " pasosA.append(a.index(i))\n", " else:\n", " pasosA.append(-(len(a)- a.index(i)))\n", "\n", "def necesariosB(a,b): # array pasosB calcula los pasos de B necesarios para colocar cada elemento de A dentro de su sitio en B\n", " for v in a:\n", " try:\n", " objetivo_primero = max([x for x in b if x 0:\n", " ra(a,b); contador += 1\n", " elif pasos < 0:\n", " rra(a,b); contador += 1\n", "\n", "def giraB(a, b, indice, pasos):\n", " global contador\n", " for i in range(abs(pasos)):\n", " if pasos > 0:\n", " rb(a,b); contador += 1\n", " elif pasos < 0:\n", " rrb(a,b); contador += 1\n", "\n", "# girando pilas A y B\n", "def giraPilas(a,b,indice): # indice es el index del valor en la pila A que deseamos poner el primero\n", " global contador\n", " if pasosA[indice] * pasosB[indice] > 0: # Existe sinergia, nos podemos ahorrar pasos\n", " pasos_comunes = min(abs(pasosA[indice]), abs(pasosB[indice]))\n", " for i in range(pasos_comunes):\n", " if pasosA[indice] > 0: # si el signo de ambos es positivo, ya que ambos tienen el mismo signo\n", " rr(a,b); contador += 1\n", " elif pasosA[indice] < 0: # si el signo de ambos es negativo\n", " rrr(a,b); contador += 1\n", " exceso_pasosA = abs(pasosA[indice]) - pasos_comunes\n", " exceso_pasosB = abs(pasosB[indice]) - pasos_comunes\n", " giraA(a, b, indice, ((pasosA[indice] > 0) - (pasosA[indice] < 0)) * exceso_pasosA) # (a > 0) - (a < 0) da el signo de a\n", " giraB(a, b, indice, ((pasosB[indice] > 0) - (pasosB[indice] < 0)) * exceso_pasosB) # Python no tiene función sign\n", " else: # No existe sinergia\n", " giraA(a ,b, indice, pasosA[indice]) # gira A\n", " giraB(a, b, indice, pasosB[indice]) # gira B" ], "metadata": { "id": "ycWnQdAMvD4h" }, "execution_count": 5, "outputs": [] }, { "cell_type": "code", "source": [ "def situarMax_en_B():\n", " indice = b.index(max(b))\n", " if indice < len(a)/2:\n", " pasos = indice\n", " else:\n", " pasos = -(len(b)- indice)\n", " giraB(a, b, indice, pasos)\n", "\n", "def subirTodo_a_A():\n", " global contador\n", " for _ in range(len(b)):\n", " pa(a,b); contador += 1" ], "metadata": { "id": "jEOhAVLnvHKS" }, "execution_count": 6, "outputs": [] }, { "cell_type": "code", "source": [ "def establece_lis(arr): # esta función solo se debería invocar una vez. Proporciona una matriz con listas de posibles lis\n", " m2 = [[0,1],[0,-1],[0,2],[0,-2],[0,3],[0,-3],[1,-1],[1,2],[1,-2],[1,3],[1,-3],[-1,2],[-1,-2],[-1,3],[-1,-3],[2,-2],[2,3],[2,-3],[-2,3],[-2,-3],[3,-3]]\n", " posibles_lis = []\n", " for pareja in m2: # m2 tiene 21 parejas\n", " x,y = pareja[0], pareja[1]\n", " lis = [arr[x], arr[y]]\n", " posibles_lis.append(lis)\n", "\n", " m3 = [[0,1,-1],[0,1,2],[0,1,-2],[0,1,3],[0,1,-3],[0,-1,2],[0,-1,-2],[0,-1,3],[0,-1,-3],[0,2,-2],[0,2,3],[0,2,-3],[0,-2,3],[0,-2,-3],[0,3,-3],[1,-1,2],[1,-1,-2],[1,-1,3],[1,-1,-3],[1,2,-2],[1,2,3],[1,2,-3],[1,-2,3],[1,-2,-3],[1,3,-3],[-1,2,-2],[-1,2,3],[-1,2,-3],[-1,-2,3],[-1,-2,-3],[-1,3,-3],[2,-2,3],[2,-2,-3],[2,3,-3],[-2,3,-3]]\n", " for trio in m3: # m3 tiene 35 trios, total len(m2)+len(m3)=21+35=56 casos posibles de lis \n", " x,y,z = trio[0], trio[1], trio[2]\n", " lis = [arr[x], arr[y], arr[z]]\n", " posibles_lis.append(lis)\n", " return posibles_lis # retorna una matriz [[a[0], a[1]], [a[0], a[-1]], [a[0], a[2]],....]" ], "metadata": { "id": "Jri41wITjp0D" }, "execution_count": 7, "outputs": [] }, { "cell_type": "code", "source": [ "if __name__ == \"__main__\": \n", " n = 100 # número de elementos de la pila\n", " limite = 700 # para n=100 limite<700, para n=500 limite<5500\n", " pasos_de_cada_intento = [0]*56 # array que contará los pasos de cada intento de tipo cero, uno, dos, tres,....\n", " a = generaPilaA(n)\n", " #print('a:', a, \"\\n\")\n", " b = []\n", " a_original = a[:]\n", " #n = len(a)\n", " posibles_lis = establece_lis(a) # llama a la función que proporciona una matriz con las posibles lis de dos números de la pila A\n", " #print(\"posibles_lis: \", posibles_lis)\n", " for intento in range(56): # intentos probando diferentes lis\n", " a = a_original[:]\n", " b = []\n", " lis = posibles_lis[intento] # establece lis que para el intento cero sería: lis = [a[0], a[1]] para el intento 1 sería: lis = [a[0], a[-1]]\n", " contador = 0 # contador de pasos\n", " rotateLIS(lis) # Llevamos de la pila A hacia la pila B los elementos de la LIS\n", " b_inicial = b[:]\n", " while len(a) > 0: # se puede mejorar siendo la condición: \"mientras la A no esté ordenada\". Nota: ver si haciendo un \"sa\" mejora algo\n", " index_minimosPasos = calculaIndexPasosMinimos()\n", " giraPilas(a,b,index_minimosPasos)\n", " pb(a,b); contador += 1 # lo pasa de A a B haciendo pb\n", " situarMax_en_B()\n", " subirTodo_a_A()\n", " print(f\"{intento+1} La pila A {'SI' if sorted(a_original)==a else 'No' } está ordenada. {'pasa' if contador