title: Efficient combinations of N colored elements with restriction in the number of colors
body: <p>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?</p>
  
  <p>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.</p>
  
  <pre><code>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) &gt; 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"
  </code></pre>
  
  <p>the output is like:</p>
  
  <pre><code>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
  
  ...
  </code></pre>
  
  <p>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.</p>