Skip to content

Instantly share code, notes, and snippets.

@abul4fia
Last active January 8, 2021 11:38
Show Gist options
  • Save abul4fia/496b6f194a6de33d356ba4343378b0e8 to your computer and use it in GitHub Desktop.
Save abul4fia/496b6f194a6de33d356ba4343378b0e8 to your computer and use it in GitHub Desktop.
Troceado óptimo
from math import ceil
def trocear_sin_minimo(lista, t_max):
"""Trocea la lista dada en el número mínimno de trozos de tamaño t_max, haciendo que
los trozos tengan todos aproximadamente el mismo tamaño"""
t_lista = len(lista)
num_trozos = int(ceil(t_lista/t_max)) # Numero de trozos a crear (y es el mínimo posible)
tam = int(ceil(t_lista/num_trozos)) # Tamaño de cada bloque "grande" (cumple tam <= t_max)
n_peq = tam * num_trozos - t_lista # Numero de bloques "pequeños" (tendrían tamaño tam-1)
n_grand = num_trozos - n_peq # Numero de bloques "grandes" (de tamaño tam)
return ( [ lista[i:i + tam] for i in range(0, n_grand*tam, tam) ]
+ [ lista[i:i + tam-1] for i in range (n_grand*tam, t_lista, tam-1)])
def trocear(lista, t_max, t_min):
"""Intenta trocear la lista dada en el mínimo número de trozos de modo que:
* Se maximice el número de trozos de tamaño t_max
* Se garantice que los restantes trozos de tamaño < t_max tienen un tamaño >= t_min
Si esto no fuera posible, llama a trocear_sin_minimo() y retorna ese resultado
"""
t_lista = len(lista)
num_trozos = int(ceil(t_lista/t_max)) # Numero de trozos a crear (y es el mínimo posible)
a_quitar = num_trozos * t_max - t_lista # Espacio sobrante a quitar de algunos trozos
n_peq = int(ceil(a_quitar / (t_max - t_min))) # Numero de trozos que tendrán un tamaño menor
if n_peq == 0:
t_peq = t_max
else:
t_peq = t_max - int(ceil(a_quitar/n_peq)) # Tamaño de cada trozo pequeño
n_grand = num_trozos - n_peq # Numero de bloques "grandes" (de tamaño tam)
if n_grand < 0: # En este caso no es posible encontrar una solución que respete t_min
return trocear_sin_minimo(lista, t_max)
trozos_grandes = [lista[i:i+t_max] for i in range(0, n_grand*t_max, t_max)]
trozos_pequeños = [lista[i:i+t_peq] for i in range(n_grand*t_max, n_grand*t_max + (n_peq-1)*t_peq, t_peq)]
trozo_final = lista[n_grand*t_max+(n_peq-1)*t_peq:]
resultado = trozos_grandes + trozos_pequeños
if trozo_final:
resultado += [trozo_final]
return resultado
from troceado import trocear
ejemplo = list(range(100))
bien = mal = 0 # Contadores de casos que respetan las restricciones o que no
problemas = [] # Lista de los casos problemáticos, por si quieres mirarlos
for t_max in range(2, 100):
for t_min in range(1, t_max):
try:
# Obtener troceado
trozos = trocear(ejemplo, t_max, t_min)
# Obtener los tamaños de cada trozo
tams = [len(t) for t in trozos]
# Obtener el conjunto de números incluidos en los trozos
# (para verificar que no haya quedado ninguno fuera por error)
incluidos = set()
for trozo in trozos:
incluidos.update(trozo)
# Verificar que la solución es correcta
assert incluidos == set(ejemplo), f"{set(ejemplo)-incluidos} no aparecen en la solucion"
assert len(incluidos) == len(ejemplo), f"Hay elementos repetidos en la solucion"
assert all(tam<=t_max for tam in tams), "Hay trozos con tamaño mayor al maximo permitido"
assert all(tam>=t_min for tam in tams), "Hay trozos con tamaño menor al minimo permitido"
bien += 1
except Exception as e:
problemas.append((t_max, t_min, tams, str(e)))
mal += 1
print(f"{bien} casos se han resuelto de forma óptima")
print(f"{mal} casos se han resuelto de forma subóptima")
# Puedes examinar la lista problemas para ver los casos subóptimos y la solución encontrada para ellos. Por ejemplo
# problemas[0] contiene
#
# (14, 13, [13, 13, 13, 13, 12, 12, 12, 12], 'Hay trozos con tamaño menor al minimo permitido'),
#
# En ese caso t_max era 14 y t_min 13.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment