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