3

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

2
  • Patricio creo que tu pregunta es realmente interesante. Que yo sepa no hay nada ya implementado para abordar un problema como este. No veo muchas posibilidades de mejora más allá de sacar [set(e) for e in no_combinables] del if para no repetir el cálculo en cada iteración y generar combinaciones_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).
    – FJSevilla
    Commented el 31 may. 2017 a las 19:04
  • Si FJSevilla, tu observación con respecto a los 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. Commented el 31 may. 2017 a las 19:14

1 respuesta 1

1

Podrías obtener un set de todos los elementos no combinables

all_no_comb=set([item for sublist in no_combinables for item in sublist]))

luego extraerlos de tu universo

universolimitado=[x for x in universo if not x in all_no_comb]

para obtener las combinaciones donde no existe probabilidad de que haya combinaciones prohibidas

noproblemcomb=[c for c in itertools.combinations(universolimitado, elementos_a_combinar)]

luego generar las combinaciones posibles de cada elemento en la lista de prohibido eliminando del propio universo de ese elemento sus combinaciones prohibidas y agregarlo a las combinaciones previamente generadas

usado=[]
for x in all_no_comb:
  universox=[y for y in all_no_comb if y != x and
             not ([x,y] in no_combinables
                  or [y,x] in no_combinables
                  or y in usado)]
  universox+=universolimitado
  combx=[]
  for c in itertools.combinations(universox, elementos_a_combinar-1):
    n=list(c)
    n.append(x)
    combx.append(tuple(n))
  noproblemcomb+=combx
  usado.append(x)
1
  • Gracias @Jorge Arturo Juarez, me gusta la idea de comenzar combinando aquellos elementos que no participan en los no_combinables, ya que parte de la solución sería encontrar al menos una combinación válida, sin embargo en la realidad del problema creo que todos los elementos del universo tienen al menos una o dos combinaciones no posibles. Como ejemplo real: al armado de una cursada, dónde una materia se da en tres días/horarios/lugares distintos, el alumno debe elegir una de las tres, obviamente las combinaciones entre ellas no son válidas ya que el alumno no va a cursar la misma materia. Commented el 11 jun. 2017 a las 16:15

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.