Combinatorial problems are known for being easy to formulate, but difficult to solve. For this, I would not use itertools at all, but instead wrote a custom generator. For example,
def combs(elt2color, combination_size=4, max_colors=3): def inner(needed, index): if needed == 0: yield result return if n - index < needed:
Then:
elt2color = dict([('A', 'red'), ('B', 'red'), ('C', 'blue'), ('D', 'blue'), ('E', 'green'), ('F', 'green'), ('G', 'green'), ('H', 'yellow'), ('I', 'white'), ('J', 'white'), ('K', 'black')]) for c in combs(elt2color): for element in c: print("%s-%s" % (element, elements[element])) print "\n"
produces the same combinations 188 as your post-processing code, but internally refuses partial combinations as soon as it spans more max_colors colors. It is not possible to change which itertools functions execute internally, so when you want to control this, you need to flip your own.
Using itertools
Here is another approach, generating first all solutions with exactly 1 color, then exactly 2 colors, etc. itertools can be used directly for most of this, but at the lowest level, a custom generator is still needed. I find it harder to understand than a fully custom generator, but it may be clearer for you:
def combs2(elt2color, combination_size=4, max_colors=3): from collections import defaultdict from itertools import combinations color2elts = defaultdict(list) for elt, color in elt2color.items(): color2elts[color].append(elt) def at_least_one_from_each(iterables, n): if n < len(iterables): return
I didn’t time them because I don’t care ;-) A fully customizable generator single result list is used repeatedly to build each output, which reduces the speed of dynamic memory. The second method creates a lot of memory garbage by combining several levels of from_first and rest tuples - and this is mostly inevitable because it uses itertools to generate from_first tuples at each level.
Inside the itertools function, itertools almost always work in a way that is more like the first code example, and for the same reasons, reuses the internal buffer as much as possible.
AND ONE MORE
This illustrates some more subtleties. I was thinking about what I would do if I implemented this functionality in C as a function of itertools . All functions of itertools were first prototyped in Python, but at a semi-low level, they come down to working with vectors of small integers (lack of an “inner loop” for using sets, dicts, slicing a sequence, or gluing a partial result of a sequence - sticking as much as possible to O(1) worst temporary operations with dirty simple native C types after initialization).
At a higher level, the itertools function would allow any iterative value as the main argument, and would almost certainly guarantee the return of combinations from a number in the lexicographic index order. So here is the code that does all this. In addition to the iterable argument, it also requires an elt2ec , which maps each element from iterable to its equivalence class (for you these are color-naming strings, but any objects used as dict keys can be used as equivalence classes):
def combs3(iterable, elt2ec, k, maxec): # Generate all k-combinations from `iterable` spanning no # more than `maxec` equivalence classes. elts = tuple(iterable) n = len(elts) ec = [None] * n # ec[i] is equiv class ordinal of elts[i] ec2j = {} # map equiv class to its ordinal for i, elt in enumerate(elts): thisec = elt2ec[elt] j = ec2j.get(thisec) if j is None: j = len(ec2j) ec2j[thisec] = j ec[i] = j countec = [0] * len(ec2j) del ec2j def inner(i, j, totalec): if i == k: yield result return for j in range(j, jbound[i]): thisec = ec[j] thiscount = countec[thisec] newtotalec = totalec + (thiscount == 0) if newtotalec <= maxec: countec[thisec] = thiscount + 1 result[i] = j yield from inner(i+1, j+1, newtotalec) countec[thisec] = thiscount jbound = list(range(n-k+1, n+1)) result = [None] * k for _ in inner(0, 0, 0): yield (elts[i] for i in result)
(Note that this is Python 3 code.) As announced, nothing in inner() is different from indexing a vector with a small integer. The only thing left to do to make it directly translate to C is delete the recursive generation. This is tiring, and since it does not illustrate anything particularly interesting here, I will ignore it.
In any case, the interesting thing is time. As noted in the comment, the synchronization results are highly dependent on the test cases you use. combs3() here the fastest, but not often! This is almost always faster than my original combs() , but usually slower than my combs2() or @GarethRees beautiful constrained_combinations() .
So, how can it be when combs3() been optimized "almost completely down to meaningless ;-) C-level operations"? Easy! It is still written in Python. combs2() and constrained_combinations() use C-coded itertools.combinations() to do most of their work, and that makes a world of difference. combs3() will run circles around them if they were encoded in C.
Of course, any of them can work unlimitedly faster than allowed_combinations() in the original message, but it can be the fastest (for example, select almost any inputs where max_colors so large that no combinations are excluded - then allowed_combinations() little effort and everyone else adds additional substantial additional overhead to “optimize” the cropping that never occurs).