Given a set of N elements colored with C colors, how can I find every possible combination of length L that contains no more than a maximum of M colors?
I tried this algorithm that uses itertools.combinations to generate all the possible combinations, and then filter out those that do not hold the maximum colors condiction.
from itertools import combinations as cb
def allowed_combinations(elements, combination_size=4, max_colors=3):
colors = set([c for k, c in elements.items()])
combinations = cb(elements, combination_size)
for combination in combinations:
colors = set([elements[element] for element in combination])
if len(colors) > max_colors:
continue
yield combination
elements = dict()
elements['A'] = 'red'
elements['B'] = 'red'
elements['C'] = 'blue'
elements['D'] = 'blue'
elements['E'] = 'green'
elements['F'] = 'green'
elements['G'] = 'green'
elements['H'] = 'yellow'
elements['I'] = 'white'
elements['J'] = 'white'
elements['K'] = 'black'
combinations = allowed_combinations(elements)
for c in combinations:
for element in c:
print("%s-%s" % (element, elements[element]))
print "\n"
the output is like:
A-red
C-blue
B-red
E-green
A-red
C-blue
B-red
D-blue
A-red
C-blue
B-red
G-green
A-red
C-blue
B-red
F-green
...
The problem is that generating all possible combinations can be computationally very expensive. In my case, for instance, L is often 6 and the number of elements N is around 50, so it gives us Bin(50,6) = 15890700 possible combinations. If maximum number of colors allowed in a comination is small, most of combinations are "useless" and so they are discarded in the filter step. My intuition is that I should put the filtering step inside/before the combinatory step, to avoid the explotion of combinations, but I don't see how.