Recursive generation + filtering. Better non-recursive ?

Question

I have the following need (in python):

• generate all possible tuples of length 12 (could be more) containing either 0, 1 or 2 (basically, a ternary number with 12 digits)
• filter these tuples according to specific criteria, culling those not good, and keeping the ones I need.

As I had to deal with small lengths until now, the functional approach was neat and simple: a recursive function generates all possible tuples, then I cull them with a filter function. Now that I have a larger set, the generation step is taking too much time, much longer than needed as most of the paths in the solution tree will be culled later on, so I could skip their creation.

I have two solutions to solve this:

1. derecurse the generation into a loop, and apply the filter criteria on each new 12-digits entity
2. integrate the filtering in the recursive algorithm, so to prevent it stepping into paths that are already doomed.

My preference goes to 1 (seems easier) but I would like to hear your opinion, in particular with an eye towards how a functional programming style deals with such cases.

Answer 1

How about

import itertools

results = []
for x in itertools.product(range(3), repeat=12):
    if myfilter(x):
        results.append(x)

where myfilter does the selection. Here, for example, only allowing result with 10 or more 1's,

def myfilter(x):  # example filter, only take lists with 10 or more 1s
    return x.count(1)>=10

That is, my suggestion is your option 1. For some cases it may be slower because (depending on your criteria) you many generate many lists that you don't need, but it's much more general and very easy to code.

Edit: This approach also has a one-liner form, as suggested in the comments by hughdbrown:

results = [x for x in itertools.product(range(3), repeat=12) if myfilter(x)]

Answer 2

itertools has functionality for dealing with this. However, here is a (hardcoded) way of handling with a generator:

T = (0,1,2)

GEN = ((a,b,c,d,e,f,g,h,i,j,k,l) for a in T for b in T for c in T for d in T for e in T for f in T for g in T for h in T for i in T for j in T for k in T for l in T)

for VAL in GEN:
    # Filter VAL
    print VAL

Answer 3

I'd implement an iterative binary adder or hamming code and run that way.