{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyPkKenxcY/PYUvV7xet/GAk", "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\n", "## Solo usando parejas para pasar de A a B los primeros números" ], "metadata": { "id": "_JPOQYd01-0C" } }, { "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": null, "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, b, contador\n", " for vlis in lis:\n", " if a.index(vlis) < len(a)/2:\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)):\n", " rra(a,b); contador += 1\n", " pb(a,b); contador += 1" ], "metadata": { "id": "8QAC4tTou36V" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# PASOS NECESARIOS PARA COLOCAR CADA ELEMENTO DE A EN SU SITIO EN B total = pasosA + pasosB (esta suma es solo una idea, se ha de sumar de una forma peculiar)\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 v in a:\n", " if a.index(v) < len(a)/2:\n", " pasosA.append(a.index(v))\n", " else:\n", " pasosA.append(-(len(a)- a.index(v)))\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 i in range(len(a)): # objetivo_primero es el número que se ha de poner en la primera posición de la pila B\n", " if a[i] < min(b): # si el elemento de A considerado es menor que el mayor de B entonces\n", " objetivo_primero = max(b) # el objetivo_primero será el mayor de B\n", " else: # objetivo_primero en este caso será el maximo de los inferiores en B al valor iésimo de A\n", " objetivo_primero = min(b) #se inicializa en el valor mínimo de la pila B\n", " for j in range(len(b)):\n", " if b[j] < a[i] and b[j] > objetivo_primero:\n", " objetivo_primero = b[j]\n", " # el objetivo_primero se ha de situar el primero de la pila B \n", " if b.index(objetivo_primero) < len(b)/2:\n", " pasosB.append(b.index(objetivo_primero))\n", " else:\n", " pasosB.append(-(len(b)- b.index(objetivo_primero)))\n", "\n", "def totaliza(a,b): # totalizar pasos\n", " global total\n", " for i in range(len(pasosA)):\n", " if pasosA[i] * pasosB[i] < 0: # si son de distinto signo, uno positivo y otro negativo\n", " total.append(abs(pasosA[i]) + abs(pasosB[i])) # no hay sinergia\n", " else: # si son de igual signo o alguno cero\n", " total.append(max(abs(pasosA[i]), abs(pasosB[i]))) # si son de igual signo hay sinergia\n", "\n", "def calculaIndexPasosMinimos():\n", " global pasosA, pasosB, total\n", " pasosA = [] # [0,1,2, ...,41,-41,... , -2,-1] vector donde cada index está asociado con el valor del mismo index en A\n", " pasosB = [] # [-3,2,-5, ..., -5,0] estos dos arrays se han de recalcular cada vez que realmente se mueva algún elemento de A a B\n", " total = []\n", " necesariosA(a, b)\n", " necesariosB(a, b)\n", " totaliza(a,b)\n", " return total.index(min(total)) # retorna el índice del elemento de la pila A que menos pasos totales necesita" ], "metadata": { "id": "ZMoJSTqfu_WV" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "def giraA(a, b, indice, pasos):\n", " global contador\n", " for i in range(abs(pasos)):\n", " if pasos > 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": null, "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": null, "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", " return posibles_lis" ], "metadata": { "id": "Jri41wITjp0D" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "if __name__ == \"__main__\":\n", " from random import seed, shuffle\n", " seed()\n", " n = 500 # número de elementos de la pila\n", " limite = 5500 # para n=100 limite<700, para n=500 limite<5500\n", " matrix_pasos = [] # matriz de pasos, los array de este array son los diferentes n_pasos otenidos en cada muestra analizada\n", " for muestra in range(2): # analizamos un cierto número de muestras de pilas A generadas de forma aleatoria\n", " n_pasos = [0]*21 # array que contendrá los pasos necesarios en cada intento de tipo cero, uno, dos, tres,.... de una muestra concreta\n", " a = list(range(1, n+1)); shuffle(a) # generación aleatoria de la pila A\n", " #print('a:', a)\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 o tres números de la pila A\n", " for intento in range(21): # vamos a probar cada pareja 21 intentos.\n", " a = a_original[:]\n", " b = []\n", " lis = posibles_lis[intento] # establece lis por ejemplo: lis = [a[0], a[1]]\n", " contador = 0 # contador de pasos\n", " rotateLIS(lis)\n", " while len(a)>0:\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", " if a != sorted(a_original): print(\"\\nERROR de ordenación\\n\")\n", " n_pasos[intento] = contador\n", " matrix_pasos.append(n_pasos)\n", " print(matrix_pasos)" ], "metadata": { "id": "iRAeorGPvLht", "colab": { "base_uri": "https://localhost:8080/" }, "outputId": "668a8526-bc90-4d81-ee41-79e3e91463f2" }, "execution_count": null, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "[[5609, 4922, 5549, 5429, 5550, 5431, 4926, 5357, 5431, 5315, 5432, 5490, 5429, 5380, 5431, 5434, 5525, 5436, 5618, 5433, 5440], [5462, 5492, 5217, 5445, 5188, 5509, 5495, 5185, 5201, 5365, 5447, 4997, 5444, 5676, 5508, 5448, 5222, 5511, 5372, 5507, 5467]]\n" ] } ] }, { "cell_type": "markdown", "source": [ "Crear un pilas28\n", "\n", "* Se pasaran los números de A a B hasta que quden 3 números en A.\n", "* En ese momento se ordenarán en A de forma creciente circular.\n", "* Luego se han de subir de B a A intercalándolos entre los números de A. \n", " - Ver que tal funciona esta posibilidad\n", "\n", "- Posteriormente ver que sucede si en lugar de parar el proceso cuando queden tres números en A, lo paramos cuando queden 5 o más.\n", "- Para ordenar esos 5, se usaría la pila B como pila auxiliar" ], "metadata": { "id": "ooWHJ-Y8kD_O" } } ] }