In [ ]:
# FUNCIONES
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
In [ ]:
# Llevamos de la pila A hacia la pila B los elementos de la LIS
def rotateLIS(lis):
global a, b, contador
for vlis in lis:
if a.index(vlis) < len(a)/2:
for i in range(a.index(vlis)):
ra(a,b); contador += 1
else:
for i in range(len(a)- a.index(vlis)):
rra(a,b); contador += 1
pb(a,b); contador += 1
In [ ]:
# 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)
def necesariosA(a, b): # array pasosA calcula los pasos necesarios para colocar cada elemento de A como el primero de su pila
for v in a:
if a.index(v) < len(a)/2:
pasosA.append(a.index(v))
else:
pasosA.append(-(len(a)- a.index(v)))
def necesariosB(a,b): # array pasosB calcula los pasos de B necesarios para colocar cada elemento de A dentro de su sitio en B
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
if a[i] < min(b): # si el elemento de A considerado es menor que el mayor de B entonces
objetivo_primero = max(b) # el objetivo_primero será el mayor de B
else: # objetivo_primero en este caso será el maximo de los inferiores en B al valor iésimo de A
objetivo_primero = min(b) #se inicializa en el valor mínimo de la pila B
for j in range(len(b)):
if b[j] < a[i] and b[j] > objetivo_primero:
objetivo_primero = b[j]
# el objetivo_primero se ha de situar el primero de la pila B
if b.index(objetivo_primero) < len(b)/2:
pasosB.append(b.index(objetivo_primero))
else:
pasosB.append(-(len(b)- b.index(objetivo_primero)))
def totaliza(a,b): # totalizar pasos
global total
for i in range(len(pasosA)):
if pasosA[i] * pasosB[i] < 0: # si son de distinto signo, uno positivo y otro negativo
total.append(abs(pasosA[i]) + abs(pasosB[i])) # no hay sinergia
else: # si son de igual signo o alguno cero
total.append(max(abs(pasosA[i]), abs(pasosB[i]))) # si son de igual signo hay sinergia
def calculaIndexPasosMinimos():
global pasosA, pasosB, total
pasosA = [] # [0,1,2, ...,41,-41,... , -2,-1] vector donde cada index está asociado con el valor del mismo index en A
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
total = []
necesariosA(a, b)
necesariosB(a, b)
totaliza(a,b)
return total.index(min(total)) # retorna el índice del elemento de la pila A que menos pasos totales necesita
In [ ]:
def giraA(a, b, indice, pasos):
global contador
for i in range(abs(pasos)):
if pasos > 0:
ra(a,b); contador += 1
elif pasos < 0:
rra(a,b); contador += 1
def giraB(a, b, indice, pasos):
global contador
for i in range(abs(pasos)):
if pasos > 0:
rb(a,b); contador += 1
elif pasos < 0:
rrb(a,b); contador += 1
# girando pilas A y B
def giraPilas(a,b,indice): # indice es el index del valor en la pila A que deseamos poner el primero
global contador
if pasosA[indice] * pasosB[indice] > 0: # Existe sinergia, nos podemos ahorrar pasos
pasos_comunes = min(abs(pasosA[indice]), abs(pasosB[indice]))
for i in range(pasos_comunes):
if pasosA[indice] > 0: # si el signo de ambos es positivo, ya que ambos tienen el mismo signo
rr(a,b); contador += 1
elif pasosA[indice] < 0: # si el signo de ambos es negativo
rrr(a,b); contador += 1
exceso_pasosA = abs(pasosA[indice]) - pasos_comunes
exceso_pasosB = abs(pasosB[indice]) - pasos_comunes
giraA(a, b, indice, ((pasosA[indice] > 0) - (pasosA[indice] < 0)) * exceso_pasosA) # (a > 0) - (a < 0) da el signo de a
giraB(a, b, indice, ((pasosB[indice] > 0) - (pasosB[indice] < 0)) * exceso_pasosB) # Python no tiene función sign
else: # No existe sinergia
giraA(a ,b, indice, pasosA[indice]) # gira A
giraB(a, b, indice, pasosB[indice]) # gira B
In [ ]:
def situarMax_en_B():
indice = b.index(max(b))
if indice < len(a)/2:
pasos = indice
else:
pasos = -(len(b)- indice)
giraB(a, b, indice, pasos)
def subirTodo_a_A():
global contador
for _ in range(len(b)):
pa(a,b); contador += 1
In [ ]:
def establece_lis(arr): # esta función solo se debería invocar una vez. Proporciona una matriz con listas de posibles lis
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]]
posibles_lis = []
for pareja in m2: # m2 tiene 21 parejas
x,y = pareja[0], pareja[1]
lis = [arr[x], arr[y]]
posibles_lis.append(lis)
return posibles_lis
In [ ]:
if __name__ == "__main__":
from random import seed, shuffle
seed()
n = 500 # número de elementos de la pila
limite = 5500 # para n=100 limite<700, para n=500 limite<5500
matrix_pasos = [] # matriz de pasos, los array de este array son los diferentes n_pasos otenidos en cada muestra analizada
for muestra in range(2): # analizamos un cierto número de muestras de pilas A generadas de forma aleatoria
n_pasos = [0]*21 # array que contendrá los pasos necesarios en cada intento de tipo cero, uno, dos, tres,.... de una muestra concreta
a = list(range(1, n+1)); shuffle(a) # generación aleatoria de la pila A
#print('a:', a)
b = []
a_original = a[:]
n = len(a)
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
for intento in range(21): # vamos a probar cada pareja 21 intentos.
a = a_original[:]
b = []
lis = posibles_lis[intento] # establece lis por ejemplo: lis = [a[0], a[1]]
contador = 0 # contador de pasos
rotateLIS(lis)
while len(a)>0:
index_minimosPasos = calculaIndexPasosMinimos()
giraPilas(a,b,index_minimosPasos)
pb(a,b); contador += 1 # lo pasa de A a B haciendo pb
situarMax_en_B()
subirTodo_a_A()
if a != sorted(a_original): print("\nERROR de ordenación\n")
n_pasos[intento] = contador
matrix_pasos.append(n_pasos)
print(matrix_pasos)
[[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]]
Crear un pilas28
- Se pasaran los números de A a B hasta que quden 3 números en A.
- En ese momento se ordenarán en A de forma creciente circular.
- Luego se han de subir de B a A intercalándolos entre los números de A.
Ver que tal funciona esta posibilidad
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.
Para ordenar esos 5, se usaría la pila B como pila auxiliar