编程挑战：笛卡尔积中的通配符排除 [英] Programming challenge: wildcard exclusion in cartesian products
问题描述
下面的python代码生成了一个笛卡尔积，它受任何
逻辑卡排除的逻辑组合的影响。例如，假设我想要
来生成[a，b，c，d]的笛卡尔乘积S ^ n，n> = 3，排除
'' * a * b *''和''* c * d * a *''。详情请参见下文。
挑战：在ruby，lisp，haskell，ocaml或
a CAS中生成等效物，如maple或mathematica。
＃---------------------------------------- ---------------------------------------
＃短算法说明
＃使用函数_gen所有程序生成
＃cartesian产品没有套装，匹配
＃some wildcarts
＃设置生成使用递归 - >
＃所有集合中的第一个将使用维度1生成，而不是通过通配符过滤
＃然后将使用维度2生成集合并再次过滤
＃，直到达到所需的设置维度
＃程序避免显式生成CP集的某些部分
＃如果whildcart的结尾是星号（*），如果
whildcart的第一部分（没有astrics）
＃匹配当前的set =>然后这个集合将被过滤掉并且不会在
中使用
＃更高维度集合生成
＃example *，1， *，2，* [1,2] dim = 10
＃by dimension 2只生成数组[1,1]，[2,1]，[2,2]
＃=> array [1,2]不会用于下一个递归级别
＃------------------------- -------------------------------------------------- ----
＃获取结果使用函数
＃CPWithoutWC第一个参数是任何元素的列表
（char，int，string ，类示例，....任何类型）
＃secont param是CP维度
＃其他参数是wildcarts =>任何值的列表然后可能
包括
＃特殊值ALL - 星号等价物
＃使用示例：命令行
＃>>> import cartesianProduct as cp
＃>>>我在cp.CPWithoutWC（[1,2]，3，[1，cp.ALL，2]）：
＃print i
＃[1,1 ，1]
＃[1,2,1]
＃[2,1,1]
＃[2,1,2] ]
＃[2,2,1]
＃[2,2,2]
＃>>>我在
cp.CPWithoutWC（[''''，''b'']，3，[''''，cp.ALL，''b'']，[ ''b''，cp.ALL，''a'']）：
＃print i
＃[''a''，''a'' ，''a'']
＃[''a''，'b''，''a'']
＃[''b'' ，''''，''b'']
＃[''b''，''b''，'b'']
＃ >>>我在cp.CPWithoutWC（[1,2]，3，[1，cp.ALL，2]，[2，cp.ALL，1]）：
＃print i
＃[1,1,1]
＃[1,2,1]
＃[2,1,2]
＃[2,2,2]
＃>>>
＃>>>我在cp.CPWithoutWC（[1,2]，121212，[1，cp.ALL]，[2，cp.ALL，1]）：
＃print i
##立即执行
＃>>>
＃如果您不想打印cp。在ALL和CPWithoutWC之前使用import
是这样的：
＃来自cartesianProduct import ALL，CPWithoutWC
＃CPWithoutWC是一个python生成器。这意味着它会立即返回值
＃并在下一个周期生成下一个。
＃程序示例
＃
##来自cartesianProduct import ALL，CPWithoutWC
## def main（）：
## for i in
cp .CPWithoutWC（[ '' A ''， '' b '']，3，[ '' A ''，cp.ALL '' b '']，[ '' b ''，cp.ALL， '' a'']）：
## ##用当前值做你想要的东西
## .........
## ##返回for语句并生成新的
## if __name__ ==" __ main __"：
## main（）
＃
"""
使用WC的逻辑组合：
1）它可以通过关于函数CPWithoutWC
前两个参数后的任意数量的通配符，例如：
CPWithoutWC（[1,2]，121212，[1，cp.ALL] ，[2，cp.ALL，1]，...）
其中...... - 是其他任何野外车的附加功能ameter。
附加WC的数量不受限制。
功能将过滤掉所有组合，这些组合与传递的任何组合相符
WC。
它等于WC1 | WC2 | ....，其中|是蟒蛇的模拟OR
逻辑运算。
2）要使用更复杂的WC组合，请按照以下步骤操作
a）首先创建所需的全部内容WC
b）然后使用运算符|，&和大括号（）创建组合
需要
然后将其传递给函数
CPWithoutWCEx作为第三个参数。不要使用或和and&
python语句，否则程序将会b / b
工作不当。此函数的前两个参数与CPWithoutWC函数的
相同 -
元素和CP维度的集合。上面在
命令行中描述的一个例子：
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 [a,b,c,d] that excludes
''*a*b*'' and ''*c*d*a*''. See below for details.
CHALLENGE: generate an equivalent in ruby, lisp, haskell, ocaml, or in
a CAS like maple or mathematica.
#-------------------------------------------------------------------------------
# Short algorithm description
# using function _genAll the program generates
# cartesian product without sets, which match
# some wildcarts
# Sets generation uses recursion ->
# first of all sets will be generated with dimension 1 and than
filtered through wildcarts
# then sets will be generated with dimension 2 and filtered again
# until the required set dimension is reached
# Program avoids explicit generation of some part of CP sets
# if the end of whildcart is asterics (*) and if the first part of
whildcart (without astrics)
# matches current set => then this set will be filtered out and won''t
be used in
# higher dimension set generation
# example *,1,*,2,* [1,2] dim = 10
# by dimension 2 only arrays [1,1],[2,1],[2,2] are will be generated
# => array [1,2] won''t be used in next recursion levels
#-------------------------------------------------------------------------------
# To obtaine result use function
# CPWithoutWC first parameter is a list of any elements
(char,int,string,class exemplar ,.... any type)
# secont param is CP dimension
# other parameters are wildcarts => lists with any values then may
include
# special value ALL - asterics equivalent
#Example of usage: command line
# >>> import cartesianProduct as cp
# >>> for i in cp.CPWithoutWC([1,2],3,[1,cp.ALL,2]):
# print i
# [1, 1, 1]
# [1, 2, 1]
# [2, 1, 1]
# [2, 1, 2]
# [2, 2, 1]
# [2, 2, 2]
# >>> for i in
cp.CPWithoutWC([''a'',''b''],3,[''a'',cp.ALL,''b''],[''b'',cp.ALL,''a'']):
# print i
# [''a'', ''a'', ''a'']
# [''a'', ''b'', ''a'']
# [''b'', ''a'', ''b'']
# [''b'', ''b'', ''b'']
# >>> for i in cp.CPWithoutWC([1,2],3,[1,cp.ALL,2],[2,cp.ALL,1]):
# print i
# [1, 1, 1]
# [1, 2, 1]
# [2, 1, 2]
# [2, 2, 2]
# >>>
# >>> for i in cp.CPWithoutWC([1,2],121212,[1,cp.ALL],[2,cp.ALL,1]):
# print i
## execute immediately
# >>>
# if You don''t want to print cp. before ALL and CPWithoutWC use import
like this:
# from cartesianProduct import ALL,CPWithoutWC
# CPWithoutWC is a python generator. Which means that it returns values
# immediately and generate next in next cycle.
# Program example
#
## from cartesianProduct import ALL,CPWithoutWC
## def main():
## for i in
cp.CPWithoutWC([''a'',''b''],3,[''a'',cp.ALL,''b''],[''b'',cp.ALL,''a'']):
## ## do what You want with current value
## .........
## ## go back to for statement and generate new
## if __name__ == "__main__":
## main()
#
"""
Using logical combinations of WC:
1) It''s possible to pass on to the function CPWithoutWC
any number of wildcarts after first two parameters, for example:
CPWithoutWC([1,2],121212,[1,cp.ALL],[2,cp.ALL,1],...)
where ... - is any other wildcart''s additional function parameters.
Number of additional WC is not limited.
Function will filter out all combinations, which match any passed on
WC.
It''s equal to WC1 | WC2 | .... , where | is python analog of OR
logical operations.
2) To use more complex WC combinations follow these steps
a) First of all create all needed WC
b) Then use operators |, & and braces () to create combinations
required and then pass it on to function
CPWithoutWCEx as the third parameter. Don''t use "or" and "and"
python statement, otherwise program will
work improper. First two parameters of this function are the same as
of CPWithoutWC function - set of
elements and CP dimension. An example of what was described above in
command line:
来自cartesianProduct import ALL，CPWithoutWC， CPWithoutWCEx，WC
a = WC（[ALL，1，ALL]）
b = WC（[ALL，2，ALL]）
c = a& b #filter out在CPWithoutWCEx（[1,2]，3，c）中匹配a和b
的所有集合：print i
[1,1,1]
[2,2,2]＃将所有1和2都存在的集合将被过滤掉
d = a | b对于我在CPWithoutWCEx中的情况（[1,2]，3，d）：打印我
＃在CPWithoutWCEx（[1,2,3]，3，d中为i返回任何内容）：打印i
[3,3,3] a = WC（[2,1，ALL]）
b = WC（[1,2，ALL]）
c = WC （[全部，2]）
d =（a | b）& c
我在CPWithoutWCEx（[1,2]，3，d）：打印i
[1,1,1]
[1,1,2]
[1,2,1]
[2,1,1]
[2,2,1]
[2,2,2]＃过滤掉所有以[1,2]或[2,1]
开头并以2结尾的组合
WC，用于形成逻辑组合不是
限制。
"""
"""
13.02.2006
a）添加了两个新功能 - CPWithoutWCEx_L和CPWithoutWC_L。
他们的界面与CPWithoutWCEx和CPWithoutWC相同
相应，除了第三个参数是WC列表和
他们严格接受三个参数。
你可以看到这些功能非常简单因为
python非常灵活=> def s（x，y）：return x * y
d = [3,2]
s（* d）## == s（3,2）
6
b）现在WC可以将字符串作为参数，你可以使用字符串
作为函数的参数CPWithoutWC和CPWithoutWC_L
而不是WC列表。
根据这些规则将字符串转换为WC
1）如果字符串中的第一个符号是
字母数字（az或AZ或0- 9）或''*''
字符字符串的每个字符都将被识别为
a distinct set element。示例：
" ad * d *" == [''''，'d''，cp.ALL，''d''，cp.ALL]
" * A * b3 *％^（''' ; == [cp.ALL，''A''，cp.ALL。''b''，''3''，cp.ALL，''％''，''（''，''''' "]
2）如果第一个字符不是（字母数字或''*''）
它将被视为分隔符。例如：
"：a：A：1：*" == [''''，''A''，''1'，cp.ALL]
" ：aA1：*" == [''aA1''，cp.ALL]
没有必要在星号周围写一些分隔符
"： aA1 *" == [''aA1''，cp.ALL]
"％aA％1 *" == [''aA''，''1''，cp .ALL]
3）如果元素中的所有非分隔和非星号字符
都是digits =>它们将被视为数字。例如：
" 123 *" == [1,2,3，cp.ALL]
"：12：3 *" == [12,3，cp.ALL]
但
"：12：a：3 *" == [''12''，''a''，'3''，cp.ALL]
使用示例：for c in cp.CPWithoutWC（[''a'' ，''b'']，3，''a * b''，'b * a''）：
打印i
[''a''''' a''，'''''
[''''，''b''，'''''
[''b' '，''''，''b'']
[''b''，''b''，''b'']我在cp.CPWithoutWC_L（[' 'a''，''b'']，3，[''a * b''，''b * a'']）：
打印i
['' a''，''''，''a'']
['''''，''b''，'''''
[''b''，''''，''b'']
[''b''，''b''，''b'']
＃你可以在cp.CPWithoutWC_L（[''''，''b'']，3，[''a * b''，[''b）混合使用字符串和野生动物列表''，cp.ALL，''a'']]）：
打印我
['''''，''''，''''']
[''''，''b''，''a'']
[''b''，''''，''b'']
[''b''，''b''，'b'']我在cp.CPWithoutWC_L（[''abc''，'''xyz'']，3，['' ：abc * xyz'']）：
from cartesianProduct import ALL,CPWithoutWC,CPWithoutWCEx,WC
a = WC([ALL,1,ALL])
b = WC([ALL,2,ALL])
c = a & b #filter out all sets which match a and b
for i in CPWithoutWCEx([1,2],3,c) : print i [1, 1, 1]
[2, 2, 2] # all sets where both 1 and 2 are present will be filtered out
d = a | b
for i in CPWithoutWCEx([1,2],3,d) : print i
# returns nothing
for i in CPWithoutWCEx([1,2,3],3,d) : print i [3, 3, 3] a = WC([2,1,ALL])
b = WC([1,2,ALL])
c = WC([ALL,2])
d = ( a | b ) & c
for i in CPWithoutWCEx([1,2],3,d) : print i [1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2, 1]
[2, 2, 2] # filters out all combinations which start with [1,2] or [2,1] and end with 2
Number of WC, which are used to form logical combinations is not
limited.
"""
"""
13.02.2006
a)Two new function - CPWithoutWCEx_L and CPWithoutWC_L are added.
Their interface is the same as of CPWithoutWCEx and CPWithoutWC
accordingly, except that the third parameter is WC list and
they accept strictly three parameters.
As You can see these functions are very simple because
python is quite flexible => def s(x,y): return x * y
d = [3,2]
s(*d) ## == s(3,2) 6
b)Now WC can take string as parameter, and You can use string
as parameters of functions CPWithoutWC and CPWithoutWC_L
instead of WC lists.
Strings transform into WC according to these rules
1)If first symbol in the string is
alphanumeric (a-z or A-Z or 0-9) or ''*''
character the every character of the string will be recognized as
a distinct set element. Examples:
"ad*d*" == [''a'',''d'',cp.ALL,''d'',cp.ALL]
"*A*b3*%^(''" == [cp.ALL,''A'',cp.ALL.''b'',''3'',cp.ALL,''%'',''('',"''"]
2)If first character is not (alphanumeric or ''*'')
it will be treated as a delimitator. Examples:
":a:A:1:*" == [''a'',''A'',''1'',cp.ALL]
":aA1:*" == [''aA1'',cp.ALL]
it''s not necessary to write delimitators around the asterics
":aA1*" == [''aA1'',cp.ALL]
"%aA%1*" == [''aA'',''1'',cp.ALL]
3)If all non delimit and non asterics character in elements
are digits => they will be treated as numbers.Examples:
"123*" == [1,2,3,cp.ALL]
":12:3*" == [12,3,cp.ALL]
but
":12:a:3*" == [''12'',''a'',''3'',cp.ALL]
Examples of use: for i in cp.CPWithoutWC([''a'',''b''],3,''a*b'',''b*a''): print i
[''a'', ''a'', ''a'']
[''a'', ''b'', ''a'']
[''b'', ''a'', ''b'']
[''b'', ''b'', ''b''] for i in cp.CPWithoutWC_L([''a'',''b''],3,[''a*b'',''b*a'']): print i
[''a'', ''a'', ''a'']
[''a'', ''b'', ''a'']
[''b'', ''a'', ''b'']
[''b'', ''b'', ''b'']
#You can mixe strings and lists for wildcarts for i in cp.CPWithoutWC_L([''a'',''b''],3,[''a*b'',[''b'',cp.ALL,''a'']]): print i
[''a'', ''a'', ''a'']
[''a'', ''b'', ''a'']
[''b'', ''a'', ''b'']
[''b'', ''b'', ''b''] for i in cp.CPWithoutWC_L([''abc'',''xyz''],3,['':abc*xyz'']):
print i
[''abc''，''abc' '，''abc'']
[''abc''，''xyz''，''abc'']
[''xyz''， ''abc''，''abc'']
[''xyz''，''abc''，''xyz'']
['' xyz''，''xyz''，''abc'']
[''xyz''，''xyz''，''xyz'']
"""
＃---------------------------------- ---------------------------------------------
class ALL（object）：传递
＃------------------------------- ------------------------------------------------ <无线电通信/>
类NO_ONE（对象）：传递
＃------------------ -------------------------------------------------- -----------
类BFunctor（对象）：
def __init __（self，func）：
self .func = func
def __call __（self，* dt，** mp）：
返回self.func（* dt，** mp）
@classmethod
def OR（cls，x，y）：
返回cls（lambda * dt，** mp：x（* dt，** mp） ）| y（* dt，** mp））
@classmethod
def AND（cls，x，y）：
返回cls（lambda） * dt，** mp：x（* dt，** mp）& y（* dt，** mp））
＃--------- -------------------------------------------------- ------------------
def __或__（self，x）：
返回BFunctor.OR（self，x ）
＃------------------------------------ -----------------------------------------
def __和__（self，x）：
返回BFunctor.AND（self，x）
＃----------------- -------------------------------------------------- ------------
def _genAll（head，n，WCF，curr）：
if len（curr）！= 0和n ！= 0：
for i in curr：
nhead = head + [i]
if n！= 1：
＃所需尺寸未达到
＃ - >我们告诉WC一些其他值
＃可能会在下一个递归级别的nhead结束时连接
＃但是如果WC以星号（ALL）结束，则比dosn没问题
＃所以我使用特殊的walue NO_ONE来解决这个问题
＃如果最后的星号如[1,2,3，ALL]的WC匹配nhead
=>
＃他们匹配nhead + [NO_ONE]到
＃但是如果WC就像[1，ALL，2,3 ] =>他们不匹配
[1,2,3，NO_ONE] =>
＃他们不能阻止生成[1,2,3,4]下一次递归
等级
x = WCF（nhead + [NO_ONE]，curr）
else：x = WCF（nhead，curr）
如果False == x：
如果n == 1：yield nhead
else：
for i in _genAll （nhead，n - 1，WCF，curr）：
收益率我
elif n == 0：
收益率头
＃--------------------------------------------- ----------------------------------
class WC（object）：
def __init __（self，wc）：
self.wc = wc
self.transformWC（）
self。 num_els = 0
self.compress（）
self.comphdr =无
self.findMaxHeader（）
self.ln = len（self.wc）
＃--------------------------- --------------------------------------------------
def transformWC（self）：
如果self.wc .__ class__不在（str，unicode）：return
if len（self。 w ^ c）== 0：返回
如果self.wc [0] .isalnum（）或self.wc [0] ==" *"：
wc = self.wc
else：
wc = self.wc [1：]。split（self.wc [0]）
nwc = []
for w in wc：
if i ==''*''：nwc.append（ALL）
elif' i中的'*''：i.split中的j为
（'''''）：
如果j：nwc.append（j）
nwc.append（ALL）
del nwc [-1]
else：nwc.append（i）
#check如果所有元素都是数字或*
allnum = True
我在nwc中：
如果我是全部：继续
尝试：int（i）
除外：
allnum = False
break
如果allnum：
for i，j in enumerate（nwc）：
如果j不是ALL：
nwc [i] = int（j）
self.wc = nwc
＃------------------------- -------------------------------------------------- -
def findMaxHeader（个体经营）：
返回
＃----- -------------------------------------------------- ----------------------
def compress（self）：
" delete dublicated * values" ;
如果len（self.wc）== 0：返回
wc_ = self.wc [：1]
for i in self .wc [1：]：
如果我= = ALL且我= = wc _ [ - 1]：继续
wc_.append（i）
self.wc = wc_
＃----------------------------- ------------------------------------------------ <无线电通信/>
def matchExact（self，hd，pos = 0）：
如果pos == len（self.wc）：return len（hd）== 0
如果self.wc [pos] == ALL：
如果pos + 1 == len（self.wc）：返回True
vl = self.wc [pos + 1]
cpos = -1
而True：
try：cpos = hd.index（vl，cpos + 1）
除外：返回False
如果self.matchExact（hd [cpos + 1：]，pos + 2）：返回True
else：
如果len（hd）== 0：返回False
如果hd [0]！= self.wc [pos]：返回False
返回sel f.matchExact（hd [1：]，pos + 1）
＃----------------------- -------------------------------------------------- ----
def __或__（self，x）：
返回BFunctor.OR（self，x）
＃ -------------------------------------------------- ---------------------------
def __和__（self，x）：
返回BFunctor.AND（self，x）
＃--------------------------- --------------------------------------------------
def __call __（self，hd，st）：
返回self.matchExact（hd）
＃-------- -------------------------------------------------- ---------------------
def CPWithoutWCEx（set，n，wc）：
for i in _genAll（[]，n，wc，set）：
收益率我
＃------------------- -------------------------------------------------- ----------
def CPWithoutWC（set，n，* dt）：
if len（dt）== 0：
wc = lambda hd，st：True
else：
wc = WC（dt [0]）
#print wc .wc
$ b我在dt [1：]中的$ b：
wc = wc | WC（i）
$ _ b $ b for i in _genAll（[]，n，wc，set）：
yield i
＃---- -------------------------------------------------- -------------------------
def CPWithoutWC_L（set，n，WCs）：
for CP in CPWithoutWC（set，n，* WCs）：
yield i
＃----------------- -------------------------------------------------- ------------
def CPWithoutWCEx_L（set，n，WCs）：
for CP in CPWithoutWCEx（set，n，* WCs） ：
收益率我
＃------------------------------ -------------------------------------------------
def main（）：
for i in CPWithoutWC_L（[''abc''，''xyz'']，3，[''：abc * xyz'' ]）：
打印我
＃---------------------------- -------------------------------------------------- -
if __name__ ==" __ main __" ：main（）
＃------------------------------------- ------------------------------------------
print i
[''abc'', ''abc'', ''abc'']
[''abc'', ''xyz'', ''abc'']
[''xyz'', ''abc'', ''abc'']
[''xyz'', ''abc'', ''xyz'']
[''xyz'', ''xyz'', ''abc'']
[''xyz'', ''xyz'', ''xyz'']
"""
#-------------------------------------------------------------------------------
class ALL(object):pass
#-------------------------------------------------------------------------------
class NO_ONE(object):pass
#-------------------------------------------------------------------------------
class BFunctor(object):
def __init__(self,func):
self.func = func
def __call__(self,*dt,**mp):
return self.func(*dt,**mp)
@classmethod
def OR(cls,x,y):
return cls(lambda *dt,**mp : x(*dt,**mp) | y(*dt,**mp))
@classmethod
def AND(cls,x,y):
return cls(lambda *dt,**mp : x(*dt,**mp) & y(*dt,**mp))
#-----------------------------------------------------------------------------
def __or__(self,x):
return BFunctor.OR(self,x)
#-----------------------------------------------------------------------------
def __and__(self,x):
return BFunctor.AND(self,x)
#-------------------------------------------------------------------------------
def _genAll(head,n,WCF,curr):
if len(curr) != 0 and n != 0:
for i in curr:
nhead = head + [i]
if n != 1 :
# needed dimension are not reached
# -> we mast tell WC that some other values
# may concatenate in the end of nhead in next recursion levels
# but if WC is ended with asterics (ALL), than dosn''t matter
# so i use special walue NO_ONE to resolve this problem
# if WC with final asterics like [1,2,3,ALL] are matched nhead
=>
# they matched nhead + [NO_ONE] to
# but if WC is like [1,ALL,2,3] => they dont match
[1,2,3,NO_ONE] =>
# they don''t prevent to generate [1,2,3,4] on next recursion
level
x = WCF(nhead + [NO_ONE],curr)
else : x = WCF(nhead,curr)
if False == x:
if n == 1 : yield nhead
else:
for i in _genAll(nhead,n - 1,WCF,curr):
yield i
elif n == 0 :
yield head
#-------------------------------------------------------------------------------
class WC(object):
def __init__(self,wc):
self.wc = wc
self.transformWC()
self.num_els = 0
self.compress()
self.comphdr = None
self.findMaxHeader()
self.ln = len(self.wc)
#-----------------------------------------------------------------------------
def transformWC(self):
if self.wc.__class__ not in (str,unicode) : return
if len(self.wc) == 0 : return
if self.wc[0].isalnum() or self.wc[0] == "*":
wc = self.wc
else:
wc = self.wc[1:].split(self.wc[0])
nwc = []
for i in wc:
if i == ''*'' : nwc.append(ALL)
elif ''*'' in i :
for j in i.split(''*''):
if j : nwc.append(j)
nwc.append(ALL)
del nwc[-1]
else : nwc.append(i)
#check if all elements are numbers or *
allnum = True
for i in nwc:
if i is ALL : continue
try : int(i)
except :
allnum = False
break
if allnum:
for i,j in enumerate(nwc):
if j is not ALL:
nwc[i] = int(j)
self.wc = nwc
#-----------------------------------------------------------------------------
def findMaxHeader(self):
return
#-----------------------------------------------------------------------------
def compress(self):
"delete dublicated * values"
if len(self.wc) == 0 : return
wc_ = self.wc[:1]
for i in self.wc[1:]:
if i == ALL and i == wc_[-1] : continue
wc_.append(i)
self.wc = wc_
#-----------------------------------------------------------------------------
def matchExact(self,hd,pos = 0):
if pos == len(self.wc) : return len(hd) == 0
if self.wc[pos] == ALL :
if pos + 1 == len(self.wc) : return True
vl = self.wc[pos + 1]
cpos = -1
while True:
try : cpos = hd.index(vl,cpos + 1)
except : return False
if self.matchExact(hd[cpos + 1:],pos + 2) : return True
else:
if len(hd) == 0 : return False
if hd[0] != self.wc[pos] : return False
return self.matchExact(hd[1:],pos + 1)
#-----------------------------------------------------------------------------
def __or__(self,x):
return BFunctor.OR(self,x)
#-----------------------------------------------------------------------------
def __and__(self,x):
return BFunctor.AND(self,x)
#-----------------------------------------------------------------------------
def __call__(self,hd,st):
return self.matchExact(hd)
#-------------------------------------------------------------------------------
def CPWithoutWCEx(set,n,wc):
for i in _genAll([],n,wc,set) :
yield i
#-------------------------------------------------------------------------------
def CPWithoutWC(set,n,*dt):
if len(dt) == 0 :
wc = lambda hd,st : True
else:
wc = WC(dt[0])
#print wc.wc
for i in dt[1:]:
wc = wc | WC(i)
for i in _genAll([],n,wc,set) :
yield i
#-------------------------------------------------------------------------------
def CPWithoutWC_L(set,n,WCs):
for i in CPWithoutWC(set,n,*WCs):
yield i
#-------------------------------------------------------------------------------
def CPWithoutWCEx_L(set,n,WCs):
for i in CPWithoutWCEx(set,n,*WCs):
yield i
#-------------------------------------------------------------------------------
def main():
for i in CPWithoutWC_L([''abc'',''xyz''],3,['':abc*xyz'']):
print i
#-------------------------------------------------------------------------------
if __name__ == "__main__" : main()
#-------------------------------------------------------------------------------
推荐答案
wk*******@cox.net 写道：
下面的python代码生成一个笛卡尔积，它受到通配符排除的任何逻辑组合的影响。例如，假设我想要生成[a，b，c，d]中的笛卡尔乘积S ^ n，n> = 3，其中不包括
''* a * b *''和'' * C * d * A * ''。请参阅下面的详细信息。
挑战：在ruby，lisp，haskell，ocaml或者像CAS或mathematica这样的CAS中生成等效物。
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 [a,b,c,d] that excludes
''*a*b*'' and ''*c*d*a*''. See below for details.
CHALLENGE: generate an equivalent in ruby, lisp, haskell, ocaml, or in
a CAS like maple or mathematica.
你的目标是什么？你想学习或引起一场火焰战争？ ;-)
无论如何，我发现这个问题很有趣，所以你走了，这里是我的
Haskell代码。如果我不关心性能，那么可能会更短。
在规范风格中写道。它也不是很有效，因为它会产生与给定模式匹配的所有列表。
在GHCi中你可以通过以下方式测试它：
What is your goal? You want to learn or to cause a flamewar? ;-)
Anyway, I found the problem entertaining, so here you go, here is my
Haskell code. It could be shorter if I didn''t care about performance and
wrote in specification style. It''s not very efficient either, because it
will generate all lists matching the given patterns.
In GHCi you can test it by:
ghci
：l WildCartesian.hs
test
我为缺乏评论而道歉。
---- 8< -------- 8< -------- 8< - ------ 8< -------- 8 LT; -------- 8 LT; -------- 8 LT; -------- 8 LT; - -
模块WildCartesian其中
导入Data.Set（设置）
导入限定的Data.Set为Set
导入Control.Monad
导入Control.Exception（断言）
导入可能
导入列表
数据Pat a = All |点亮一个派生表演
generateMatching ::（Ord a）=> Int - >设置 - > [Pat a] - > [[a]]
generateMatching 0 _ [] = [[]]
generateMatching 0 _（_：_）= []
generateMatching len alphabet（Lit x：ps）
| x`Set.member` alphabet =
[（x：xs）| xs< - generateMatching（len - 1）字母ps]
|否则=
[]
generateMatching len alphabet（全部：ps）=
[（x：xs）
| x< - Set.toList alphabet
，xs< - unionSorted
（generateMatching（len - 1）alphabet ps）
（generateMatching （len - 1）字母表（全部：ps））]
`unionSorted`
generateMatching len alphabet ps
generateMatching _ _ [] = []
generateNotMatching ::（Ord a）=> [a] - > Int - > [[pat a]] - > [[a]]
generateNotMatching alphabet len patterns =
generateMatching len alphaSet [All]
`sundractSorted`
foldr unionSorted []
（map（generateMatching len alphaSet .simplifiedPat）模式）
其中
alphaSet = Set.fromList alphabet
simplifyPat（全部：全部：ps）= simplifyPat（全部：ps）
simplifyPat（p：ps）= p：simplifyPat ps
simplifyPat [] = []
joinSorted :: Ord a => [a] - > [a] - > [（也许是，也许是）]
joinSorted（x1：x2：_）_ | assert（x1< x2）False = undefined
joinSorted _（y1：y2：_）|断言（y1< y2）False =未定义
joinSorted（x：xs）（y：ys）=
案例x`比较'y
LT - > （只是x，没什么）：joinSorted xs（y：ys）
EQ - > （只是x，只是y）：joinSorted xs ys
GT - > （没什么，只是y）：joinSorted（x：xs）ys
joinSorted（x：xs）[] =（只是x，没什么）：joinSorted xs []
joinSorted []（y：ys）=（没什么，只是y）：joinSorted [] ys
joinSorted [] [] = []
unionSorted： ：Ord a => [a] - > [a] - > [a]
unionSorted xs ys = catMaybes（map（uncurry mplus）（joinSorted xs ys））
subtractSorted :: Ord a => [a] - > [a] - > [a]
subtractSorted xs ys = catMaybes（map f（joinSorted xs ys））
where
f（Just x，Nothing）= Just x
f _ =没什么
test = do
t [1,2] 3 [[Lit 1，All，Lit 2] ]]
t [''''，''b''] 3 [[点亮''''，全部，点亮''b'']，[点亮''b'' ，All，Lit''a'']]
t [1,2] 3 [[Lit 1，All，Lit 2]，[Lit 2，All，Lit 1]]
其中
tabc = do
putStrLn（concat（intersperse"" [" generateMatching"，show a，show b，show c]））
mapM_（putStrLn。（"" ++）。show）（generateNotMatching abc）
---- 8< -------- 8< -------- 8 LT; -------- 8 LT; -------- 8 LT; -------- 8 LT; -------- 8 LT; -------- 8< ----
最好的问候
Tomasz
- -
我正在寻找至少在
（Haskell || ML）&& （Linux || FreeBSD || math）
在波兰华沙工作
ghci
:l WildCartesian.hs
test
I apologise for the lack of comments.
----8<--------8<--------8<--------8<--------8<--------8<--------8<--------8<----
module WildCartesian where
import Data.Set (Set)
import qualified Data.Set as Set
import Control.Monad
import Control.Exception (assert)
import Maybe
import List
data Pat a = All | Lit a deriving Show
generateMatching :: (Ord a) => Int -> Set a -> [Pat a] -> [[a]]
generateMatching 0 _ [] = [[]]
generateMatching 0 _ (_:_) = []
generateMatching len alphabet (Lit x : ps)
| x `Set.member` alphabet =
[ (x : xs) | xs <- generateMatching (len - 1) alphabet ps ]
| otherwise =
[ ]
generateMatching len alphabet (All : ps) =
[ (x : xs)
| x <- Set.toList alphabet
, xs <- unionSorted
(generateMatching (len - 1) alphabet ps)
(generateMatching (len - 1) alphabet (All : ps)) ]
`unionSorted`
generateMatching len alphabet ps
generateMatching _ _ [] = []
generateNotMatching :: (Ord a) => [a] -> Int -> [[Pat a]] -> [[a]]
generateNotMatching alphabet len patterns =
generateMatching len alphaSet [All]
`subtractSorted`
foldr unionSorted []
(map (generateMatching len alphaSet . simplifyPat) patterns)
where
alphaSet = Set.fromList alphabet
simplifyPat (All : All : ps) = simplifyPat (All : ps)
simplifyPat (p : ps) = p : simplifyPat ps
simplifyPat [] = []
joinSorted :: Ord a => [a] -> [a] -> [(Maybe a, Maybe a)]
joinSorted (x1:x2:_) _ | assert (x1 < x2) False = undefined
joinSorted _ (y1:y2:_) | assert (y1 < y2) False = undefined
joinSorted (x:xs) (y:ys) =
case x `compare` y of
LT -> (Just x, Nothing) : joinSorted xs (y:ys)
EQ -> (Just x, Just y) : joinSorted xs ys
GT -> (Nothing, Just y) : joinSorted (x:xs) ys
joinSorted (x:xs) [] = (Just x, Nothing) : joinSorted xs []
joinSorted [] (y:ys) = (Nothing, Just y) : joinSorted [] ys
joinSorted [] [] = []
unionSorted :: Ord a => [a] -> [a] -> [a]
unionSorted xs ys = catMaybes (map (uncurry mplus) (joinSorted xs ys))
subtractSorted :: Ord a => [a] -> [a] -> [a]
subtractSorted xs ys = catMaybes (map f (joinSorted xs ys))
where
f (Just x, Nothing) = Just x
f _ = Nothing
test = do
t [1,2] 3 [[Lit 1, All, Lit 2]]
t [''a'',''b''] 3 [[Lit ''a'', All, Lit ''b''], [Lit ''b'', All, Lit ''a'']]
t [1,2] 3 [[Lit 1, All, Lit 2], [Lit 2, All, Lit 1]]
where
t a b c = do
putStrLn (concat (intersperse " " ["generateMatching", show a, show b, show c]))
mapM_ (putStrLn . (" "++) . show) (generateNotMatching a b c)
----8<--------8<--------8<--------8<--------8<--------8<--------8<--------8<----
Best regards
Tomasz
--
I am searching for programmers who are good at least in
(Haskell || ML) && (Linux || FreeBSD || math)
for work in Warsaw, Poland
Tomasz Zielonka写道：
Tomasz Zielonka wrote:
putStrLn（concat（intersperse"" [" generateMatching"，show a，show b，show c]））
putStrLn (concat (intersperse " " ["generateMatching", show a, show b, show c]))
小修正：它应该是 generateNotMatching" ;.
祝你好运
Tomasz
-
我是寻找至少在
（Haskell || ML）&& （Linux || FreeBSD || math）
在波兰华沙工作
Minor correction: it should be "generateNotMatching".
Best regards
Tomasz
--
I am searching for programmers who are good at least in
(Haskell || ML) && (Linux || FreeBSD || math)
for work in Warsaw, Poland
这篇关于编程挑战：笛卡尔积中的通配符排除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
