# wildcard exclusion in cartesian products

John Zenger john_zenger at yahoo.com
Mon Mar 27 03:32:34 CEST 2006

```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:
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.
>
>
> 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
>
>     if p==[]: return []
>     else:
>        h=p
>        t=p[1:]
>        if h != '*':
>           if h == x: return [t]
>           else: return []
>        else: return [p] + [t] + advancePattern(x,t)
>
>     aP=[]
>     for p in 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: