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 ##---------------------------- -- http://mail.python.org/mailman/listinfo/python-list