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
# 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 [set(e) for e in no_combinables]):
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?
NOTANOTAS: En un caso real, la lista de "no combinables" es mucho mayor