wildcard exclusion in cartesian products

[John Zenger]

A quick fix:  change your last two functions to:

def generateNotMatching(A,n,P):
     for g in gen(A,n,P,[]):
         for x in g:
             yield x

def gen(A,n,P,acc):
     if any(imap((lambda p:  allStar(p) and notNullOrZero(p,n)), P)):
        yield []
     else:
        if n==0:
           yield map(rev,[acc])
        else:
           for a in A:
               for xx in gen(A,n-1,advancePatterns(a,P),[a]+acc):
                   yield xx

For the most part, just replace return with yield.

By the way:  you are reinventing the wheel with imap and rev.  imap is 
itertools.imap.  rev(L) is the same as L[:-1].

wkehowski at cox.net wrote:
> The python code below is adapted from a Haskell program written by
> Tomasz
> Wielonka on the comp.lang.functional group. It's more verbose than his
> since I wanted to make sure I got it right.
> 
> http://groups.google.com/group/comp.lang.functional/browse_frm/thread...
> 
> Does anyone know how to turn it into a module (or whatever it's called)
> so that I can put it in a
> loop and not have to generate the whole list? I've already tried
> without success.
> 
> The program solves the following problem: generate the subset X of the
> cartesian product S^n that excludes n-tuples defined by wildcards. For
> example, if I want to exclude from [1,2,3]^3 the wc's [1,"*",2] and
> ["*",3,"*",3,"*"], where "*" stands for a sequence of zero or more
> elements of [1,2,3], then I just type
> 
> for x in generateNotMatching([1,2,3,4],4,[[1,'*',2],[3,'*',4]]): print
> x
> 
> and get the output
> 
>                            [1, 1, 1]
>                            [1, 1, 3]
>                            [1, 2, 1]
>                            [1, 2, 3]
>                            [1, 3, 1]
>                            [2, 1, 1]
>                            [2, 1, 2]
>                            [2, 1, 3]
>                            [2, 2, 1]
>                            [2, 2, 2]
>                            [2, 2, 3]
>                            [2, 3, 1]
>                            [2, 3, 2]
>                            [3, 1, 1]
>                            [3, 1, 2]
>                            [3, 2, 1]
>                            [3, 2, 2]
> 
> This is nice! But all elements are generated before they are printed.
> 
> ##----------------------------
> import sys, os, string
> 
> def imap(function, source):
>     for element in source:
>         yield function(element)
> 
> def any(iterable):
>      '''True iff at least one element of the iterable is True'''
>      for element in iterable:
>         if element:
>             return True # or element and change the definition
>      return False
> 
> def all(iterable):
>      '''True iff no element of the iterable is True'''
>      '''SHOULD BE?: True iff all element of the iterable are True'''
>      for element in iterable:
>         if not element:
>             return False
>      return True
> 
> def rev(L):
>     rL=[]
>     for x in L: rL=[x]+rL
>     return rL
> 
> def advancePattern(x,p):
>     if p==[]: return []
>     else:
>        h=p[0]
>        t=p[1:]
>        if h != '*':
>           if h == x: return [t]
>           else: return []
>        else: return [p] + [t] + advancePattern(x,t)
> 
> def advancePatterns(x,P):
>     aP=[]
>     for p in P:
>         aP += advancePattern(x,p)
>     return aP
> 
> #    return [advancePattern(x,p) for p in P]
> 
> def allStar(p):
>     return all( imap((lambda x: x=='*'),p) )
> 
> def notNullOrZero(p,n):
>     return p !=[] or n==0
> 
> def generateNotMatching(A,n,P):
>     return gen(A,n,P,[])
> 
> def gen(A,n,P,acc):
>     if any(imap((lambda p:  allStar(p) and notNullOrZero(p,n)), P)):
>        return []
>     else:
>        if n==0:
>           return map(rev,[acc])
>        else:
>           aG=[]
>           for a in A:
>               aG += gen(A,n-1,advancePatterns(a,P),[a]+acc)
>           return aG
> 
> ##----------------------------
>