hoy vengo a plantear un problema, más de algoritmo que de lenguaje. Necesito llegar a generar una, varias, o todas las combinaciones posibles de 25 elementos, (o incluso me conformaría al menos con una combinación con la mayor cantidad de elementos posibles) sobre un universo de 75, pero, con la salvedad que no todos los elementos son combinables entre si. La propiedad de "no combinabilidad" se podría manejar en una lista aparte dónde tendríamos tuplas/listas del tipo (elemento1, elemento2)
, vale decir, que si tengo una posible combinación con 25 elementos, pero en ella se encuentra alguna de las tuplas/listas de los "no combinables" se invalidaría toda la combinación.
Lo que tengo desarrollado es:
import itertools
universo = ['GA', 'RR', 'ZO', 'CU', 'VK', 'HU', 'OF', 'ER', 'RF', 'BI', 'NX', 'OE', 'HD', 'QG', 'EG', 'YY', 'JV', 'OW', 'KU', 'WU', 'TO', 'DR', 'TX', 'NG', 'DC', 'QF', 'VL', 'EU', 'TI', 'XA', 'MN', 'GP', 'FY', 'YC', 'FK', 'TH', 'MP', 'QR', 'LO', 'PX', 'CX', 'MT', 'LK', 'IN', 'XO', 'YV', 'DE', 'MW', 'SV', 'TC', 'TJ', 'QL', 'XX', 'HH', 'RA', 'WH', 'HS', 'GB', 'KG', 'GF', 'MH', 'QU', 'LA', 'GS', 'BA', 'UR', 'JB', 'ZH', 'SU', 'KN', 'WY', 'XI', 'PV', 'BC']
no_combinables = [ ['DC', 'QF'],
['DC', 'RA'],
['WH', 'QG'],
['KU', 'YV'],
['KU', 'HS'],
['KU', 'VK']
]
combinaciones_posibles = []
elementos_a_combinar = 3
total_combinaciones = 0
no_combinables_sets = [set(e) for e in no_combinables]
# Genero todas las combinaciones
for c in itertools.combinations(universo, elementos_a_combinar):
# Verifico si alguno de los "no combinables" está en esta combinación en cuyo caso no sirve
if not any(s.issubset(c) for s in no_combinables_sets):
combinaciones_posibles.append(c)
total_combinaciones += 1
print("Total de combinaciones posibles de {} elementos: {} de {}".format(elementos_a_combinar, len(combinaciones_posibles), total_combinaciones))
Esto funciona cuando armo combinaciones de pocos elementos, obviamente llegar a lo que quiero que es generar las combinaciones de 25 de 75 elementos es impracticable, por lo que me pregunto: ¿hay en el lenguaje alguna forma de resolver este problema? o ¿Existe una aproximación distinta a este problema?
NOTAS: En un caso real, la lista de "no combinables" es mucho mayor
[set(e) for e in no_combinables]
delif
para no repetir el cálculo en cada iteración y generarcombinaciones_posibles
usando compresión de listas. Esto realmente no aporta mucho ya que la carga está realmente en generar las combinaciones (muchas de ellas inválidas), la clave creo que es encontrar la forma de no generar las combinaciones prohibidas directamente (en vez de filtrarlas como haces ahora).no_combinables
es buena. Con respecto a la solución, no pude salir de la idea de recorrer todas las combinaciones, una posible mejora es ordenar la lista del universo, por aquellos elementos que sean más combinables que otros y de esa forma al menos encontrar más rápido un caso (conformarse con uno) y salir del ciclo.