Considere el siguiente ejemplo:
import itertools import numpy as np a = np.arange(0,5) b = np.arange(0,3) c = np.arange(0,7) prods = itertools.product(a,b,c) for p in prods: print(p)
Esta iteración sobre los productos en el siguiente orden:
(0, 0, 0) (0, 0, 1) (0, 0, 2) (0, 0, 3) (0, 0, 4) (0, 1, 0)
Pero preferiría tener los productos dados en orden de su suma , por ejemplo
(0, 0, 0) (0, 0, 1) (0, 1, 0) (1, 0, 0) (0, 1, 1) (1, 0, 1) (1, 1, 0) (0, 0, 2)
¿Cómo puedo lograr esto sin almacenar todas las combinaciones en la memoria?
Nota: a
b
y c
son siempre rangos, pero no necesariamente con el mismo máximo. Tampoco hay ordenación de segundo nivel cuando las sumas de dos productos son iguales, es decir, (0,1,1)
es equivalente a (2,0,0)
.
Si los pasos son siempre 1 y evitar almacenar todas las combinaciones es su máxima prioridad, podría hacer lo siguiente (usando parcialmente itertools.product ):
import itertools import numpy as np def weak_compositions(boxes, balls, parent=tuple()): """https://stackoverflow.com/a/36748940/4001592""" if boxes > 1: for i in range(balls + 1): for x in weak_compositions(boxes - 1, i, parent + (balls - i,)): yield x else: yield parent + (balls,) def verify_limits(x, minimum, maximum): all_max = all(xi <= li for xi, li in zip(x, maximum)) all_min = all(xi >= li for xi, li in zip(x, minimum)) return all_max and all_min def iterate_in_sum(ranges): prods = itertools.product(*ranges) # find number of different sums unique_total_sums = sorted(set(sum(p) for p in prods)) # find the minimum limits minimum_allowed = [min(r) for r in ranges] # find the maximum limits maximum_allowed = [max(r) for r in ranges] for total_sum in unique_total_sums: # decompose each sum into its summands for x in weak_compositions(len(ranges), total_sum): # if the decomposition meets the limits if verify_limits(x, minimum_allowed, maximum_allowed): yield x a = np.arange(0, 5) b = np.arange(0, 3) c = np.arange(0, 7) for s in iterate_in_sum([a, b, c]): print(s, sum(s))
Salida (parcial)
(0, 0, 0) 0 (1, 0, 0) 1 (0, 1, 0) 1 (0, 0, 1) 1 (2, 0, 0) 2 (1, 1, 0) 2 (1, 0, 1) 2 (0, 2, 0) 2 (0, 1, 1) 2 (0, 0, 2) 2 (3, 0, 0) 3 (2, 1, 0) 3 (2, 0, 1) 3 (1, 2, 0) 3 (1, 1, 1) 3 (1, 0, 2) 3 (0, 2, 1) 3 (0, 1, 2) 3
El núcleo de la solución es la función weak_compositions
que descompondrá un número en sus sumandos (algo así como una partición entera ). Aquí se pueden encontrar más soluciones al problema anterior de composición de n en k partes.
Nota :
La solución se puede extender a pasos no uniformes con costo de complejidad adicional.
La forma más fácil de hacer esto sin almacenar productos adicionales en la memoria es recursiva. En lugar de range(a,b)
, pase una lista de pares (a,b)
y haga la iteración usted mismo:
def prod_by_sum(range_bounds: List[Tuple[int, int]]): """ Yield from the Cartesian product of input ranges, produced in order of sum. >>> range_bounds = [(2, 4), (3, 6), (0, 2)] >>> for prod in prod_by_sum(range_bounds): ... print(prod) (2, 3, 0) (2, 3, 1) (2, 4, 0) (3, 3, 0) (2, 4, 1) (2, 5, 0) (3, 3, 1) (3, 4, 0) (2, 5, 1) (3, 4, 1) (3, 5, 0) (3, 5, 1) """ def prod_by_sum_helper(start: int, goal_sum: int): low, high = range_bounds[start] if start == len(range_bounds) - 1: if low <= goal_sum < high: yield (goal_sum,) return for current in range(low, min(high, goal_sum + 1)): yield from ((current,) + extra for extra in prod_by_sum_helper(start + 1, goal_sum - current)) lowest_sum = sum(lo for lo, hi in range_bounds) highest_sum = sum(hi - 1 for lo, hi in range_bounds) for goal_sum in range(lowest_sum, highest_sum + 1): yield from prod_by_sum_helper(0, goal_sum)
que tiene salida para range_bounds = [(0, 5), (0, 3), (0, 7)]
comenzando con:
(0, 0, 0) (0, 0, 1) (0, 1, 0) (1, 0, 0) (0, 0, 2) (0, 1, 1) (0, 2, 0) (1, 0, 1) (1, 1, 0) (2, 0, 0)
Puede realizar este proceso exacto de manera iterativa modificando una sola lista y generando copias de ella, pero el código se vuelve más complicado o menos eficiente.
También puede modificar esto de manera trivial para admitir pasos además de 1, sin embargo, eso funciona de manera menos eficiente con pasos cada vez más grandes, ya que el último rango podría no contener el elemento necesario para producir la suma actual. Eso parece inevitable, porque en ese momento necesitaría resolver un problema computacional difícil para recorrer de manera eficiente esos productos por suma.