How to solve a combinatorial problem, preferably in python?

Question

How to solve a combinatorial problem, preferably in python?

Navigation

#1 by (1 votes)

3

Today I come to pose a problem, more of algorithm than of language. I need to get to generate one, several, or all the possible combinations of 25 elements, (or I would even be satisfied with at least one combination with as many elements as possible) over a universe of 75, but with the exception that not all Elements are combinable with each other. The property of "non-combinability" could be handled in a separate list where we would have tuples / lists of type (elemento1, elemento2) , that is, if I have a possible combination with 25 elements, but in it there is one of the tuples / lists of the "non-combinable" would invalidate the entire combination.

What I have developed is:

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))

This works when I assemble combinations of few elements, obviously to get what I want to generate the combinations of 25 out of 75 elements is impractical, so I ask myself: is there any way to solve this problem in the language? or Is there a different approach to this problem?

NOTES: In a real case, the list of "non-combinable" is much larger

python python-3.x algoritmos

asked by Patricio Moracho 31.05.2017 в 18:44

source

1 answer

Problems connecting to multiple github accounts with different ssh keys Custom adapter adds rows when scrolling

score 1 · Answer 1

You could get a set of all non-combinable items

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

then extract them from your universe

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

to obtain combinations where there is no likelihood of prohibited combinations

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

then generate the possible combinations of each element in the forbidden list by eliminating its prohibited combinations from the universe of that element and adding it to previously generated combinations

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)