{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyOxJx3GSN1xgbC8wRelsrvb", "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": [ "# Determinación del nº de tramos óptimo ```s``` para cada ```n```" ], "metadata": { "id": "7lqQLFfXjWNt" } }, { "cell_type": "code", "execution_count": 1, "metadata": { "id": "NLkJfoF-jJDx" }, "outputs": [], "source": [ "# FUNCIONES\n", "from random import sample, seed\n", "seed()\n", "\n", "def lista_ordenada(lis, orden_inverso=False): # la función da True si ponemos lista_ordenada([4,3,2,1], orden_inverso=True)\n", " ordenada = False\n", " aux = lis[:]\n", " aux.sort(reverse=orden_inverso)\n", " if aux == lis:\n", " ordenada = True\n", " return ordenada\n", "\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\n", "\n", "def separa(tramo, n, s, a, b): # se llevan de la pila A a la B los números del tramo que toca\n", " contador = 0\n", " ancho = int(n/s)\n", " fin = tramo * ancho # fin del tramo\n", " inicio = (tramo-1)*ancho+1 # inicio del tramo\n", " pasados = 0 # cuenta cuantos números se han pasado de la pila A a la B\n", " while pasados < fin-inicio+1: # recorremos los elementos de la plia A hasta que pasemos todos los números de este tramo\n", " if inicio <= a[0] <= fin:\n", " pb(a,b)\n", " contador += 1\n", " pasados += 1\n", " else:\n", " ra(a,b)\n", " contador += 1\n", " return a, b, contador\n", "\n", "def ordena(tramo, n, s, a, b): # Pasamos de B a A los del tramo que toca, comenzando por el nº mayor, que para el tramo 1 es 5.\n", " # ordena los números recientemente separados y llevados a B\n", " # el objetivo es que esos números queden en B ordenados de forma decreciente: 5,4,3,2,1\n", " contador = 0\n", " ancho = int(n/s)\n", " fin = tramo * ancho # fin del tramo\n", " inicio = (tramo-1)*ancho+1 # inicio del tramo\n", " while not lista_ordenada(b, orden_inverso=True): # se repite hasta que B quede ordenada decrecientemente. Si solo queda un elemento en B es que está ordenada\n", " while max(b) != b[0]: # buscamos el máximo y vamos haciendo ra o rra hasta que quede el primero\n", " if b.index(max(b)) <= int(len(b)/2):\n", " rb(a,b)\n", " else:\n", " rrb(a,b)\n", " contador += 1\n", " if not lista_ordenada(b, orden_inverso=True):\n", " pa(a,b); contador += 1\n", " while len(a) > n-fin: # llevamos de A a B los números del tramo que toca\n", " pb(a,b); contador += 1\n", " return a, b, contador\n", "\n", "def ordena_final(tramo, n, s, a, b): # ordena los números del úlitmo tramo que están en \"A\" y el objetivo es que queden crecientes: ...,18,19,20.\n", " contador = 0\n", " ancho = int(n/s)\n", " fin = n # en el último tramo se ajusta para que el último nº sea igual a n\n", " inicio = (tramo-1)*ancho+1 # inicio del tramo\n", " while not lista_ordenada(a): # se repite hasta que A quede ordenada en orden creciente. Si solo queda un elemento en A es que está ordenada\n", " while min(a) != a[0]:\n", " if a.index(min(a)) <= int(len(a)/2):\n", " ra(a,b)\n", " else:\n", " rra(a,b)\n", " contador += 1\n", " if not lista_ordenada(a):\n", " pb(a,b); contador += 1\n", " while len(b) > 0: # llevamos de B a A todos los números que hay en B\n", " pa(a,b); contador += 1\n", " return a, b, contador" ] }, { "cell_type": "code", "source": [ "if __name__ == \"__main__\":\n", " for n in [100]:\n", " for generada in range(100): # nº de pilas A generadas por cada n\n", " # Generación de la pila a\n", " #n = 500 # número de elementos de la pila\n", " a = sample(range(1, n+1), n)\n", " a_original = a[:]\n", " b = []\n", " ###### PROCEDIMIENTO PRIMERO ######\n", " contador = 0\n", " while not lista_ordenada(a): # se repite hasta que A quede ordenada. Si solo queda un elemento en A es que está ordenada\n", " while min(a) != a[0]: # buscamos el mínimo y vamos haciendo ra o rra hasta que quede el primero\n", " if a.index(min(a)) <= int(len(a)/2):\n", " ra(a,b)\n", " else:\n", " rra(a,b)\n", " contador += 1\n", " if not lista_ordenada(a):\n", " pb(a,b); contador += 1 #print(a,b) # luego hacemos pb\n", " while len(b) > 0: # luego se hace pa pa pa pa hasta que no quede nadie en la pila b\n", " pa(a,b); contador += 1\n", " #print(\"PROCEDIMIENTO PRIMERO contador:\", contador)\n", " primero = contador\n", " for s in range(2,11):\n", " ###### PROCEDIMIENTO SEGUNDO ######\n", " a = a_original[:]\n", " n = len(a)\n", " b = []\n", " #s = 20 # número de grupos\n", " contador = 0\n", " for tramo in range(1, s): # tramo=1,2,...,s-1. El último tramo se trata de forma diferente\n", " a, b, contador_separa = separa(tramo,n,s,a,b) # lleva de A a B los números correspondientes a ese tramo\n", " contador += contador_separa\n", " a, b, contador_ordena = ordena(tramo,n,s,a,b) # ordena los números recientemente separados y llevados a B\n", " contador += contador_ordena\n", " # tramo final donde los números de A ya se ordenan en A, ya no se usa la función separa\n", " # la pila de trabajo es \"A\" y el objetivo es que sea creciente: ...,18,19,20.\n", " a, b, contador_ordena_final = ordena_final(tramo,n,s,a,b)\n", " contador += contador_ordena_final\n", " #print(\"Al final:\", a, b)\n", " #print(\"PROCEDIMIENTO SEGUNDO contador: \", contador)\n", " segundo=contador\n", " #print(f\"n: {n}, primero: {primero}, s: {s}, segundo: {segundo}\")\n", " print(n,primero,s,segundo)" ], "metadata": { "id": "05hmY68nmHFc" }, "execution_count": null, "outputs": [] } ] }