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:
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
>
> ##----------------------------
>
More information about the Python-list
mailing list