473,322 Members | 1,398 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

wildcard exclusion in cartesian products

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....wse_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

##----------------------------

Mar 26 '06 #1
3 1250
wk*******@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....wse_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.
I know next to nothing about Haskell, but I believe that it evaluates sequences
lazily by default. Python can certainly do lazy evaluation, but you'll have to
ask for it explicitly.
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


[I think your example and test case may have become mixed up]
....

Here's an iterative "lazy" solution. While we're at it, why not use re for
pattern matching, rather than rolling our own matcher (this does restrict the
set members to characters, maybe that's OK):

import re

def cp_excl_wc(alpha, N, *exclusions):
RE0, RE1 = compile_re(exclusions)
def add_one(outer, RE_PATTS):
if RE_PATTS:
for partial in outer:
for a in alpha:
next = partial + a
if not RE_PATTS.match(next):
yield next
else: # if there's no pattern to match at this length
# don't waste time trying
for partial in outer:
for a in alpha:
yield partial+a
cpgen = "",
# RE0 holds the patterns that match at the beginning, so are tested
# against all iterations less than full length
for n in range(N-1):
cpgen = add_one(cpgen, RE0)
# For the last place, test the full-length patterns
cpgen = add_one(cpgen, RE1)
return cpgen
def compile_re(exclusions):
re0 = [] # patterns that can be matched anywhere
re1 = [] # patterns that match only the full-length
for pattern in exclusions:
pattern = pattern.replace("*", ".*")
if pattern.endswith(".*"):
re0.append(pattern)
re1.append(pattern+"$")

re0 = re0 and re.compile("|".join(re0)) or None
re1 = re1 and re.compile("|".join(re1)) or None
return re0, re1
nm = cp_excl_wc("123",3,"1*2","3*1")
nm.next() '111' nm.next() '113' nm.next() '121' nm.next() '123' list(nm) ['131', '133', '211', '212', '213', '221', '222', '223', '231', '232', '233',
'312', '313', '322', '323', '332', '333']


Is this the sort of thing you had in mind?

Michael

Mar 26 '06 #2
Michael,

Yes! That is precisely what I had in mind!

Thanks,

Walter Kehowski

Mar 26 '06 #3
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].

wk*******@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....wse_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

##----------------------------

Mar 27 '06 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

78
by: wkehowski | last post by:
The python code below generates a cartesian product subject to any logical combination of wildcard exclusions. For example, suppose I want to generate a cartesian product S^n, n>=3, of that...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.