Troceado óptimo

troceado.py

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

troceado_test.py

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.