编程挑战：笛卡尔积中的通配符排除

本文介绍了编程挑战：笛卡尔积中的通配符排除的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 下面的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 anylogical combination of wildcard exclusions. For example, suppose I wantto 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 ina 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 thanfiltered 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 ofwhildcart (without astrics)# matches current set => then this set will be filtered out and won''tbe 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 mayinclude# 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 incp.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 importlike 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 incp.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 CPWithoutWCany 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 onWC.It''s equal to WC1 | WC2 | .... , where | is python analog of ORlogical operations.2) To use more complex WC combinations follow these stepsa) First of all create all needed WCb) Then use operators |, & and braces () to create combinationsrequired and then pass it on to functionCPWithoutWCEx as the third parameter. Don''t use "or" and "and"python statement, otherwise program willwork improper. First two parameters of this function are the same asof CPWithoutWC function - set ofelements and CP dimension. An example of what was described above incommand line: 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 = funcdef __call__(self,*dt,**mp):return self.func(*dt,**mp)@classmethoddef OR(cls,x,y):return cls(lambda *dt,**mp : x(*dt,**mp) | y(*dt,**mp))@classmethoddef 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 recursionlevelx = WCF(nhead + [NO_ONE],curr)else : x = WCF(nhead,curr)if False == x:if n == 1 : yield nheadelse:for i in _genAll(nhead,n - 1,WCF,curr):yield ielif n == 0 :yield head#-------------------------------------------------------------------------------class WC(object):def __init__(self,wc):self.wc = wcself.transformWC()self.num_els = 0self.compress()self.comphdr = Noneself.findMaxHeader()self.ln = len(self.wc) #-----------------------------------------------------------------------------def transformWC(self):if self.wc.__class__ not in (str,unicode) : returnif len(self.wc) == 0 : returnif self.wc[0].isalnum() or self.wc[0] == "*":wc = self.wcelse: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 = Truefor i in nwc:if i is ALL : continuetry : int(i)except :allnum = Falsebreakif 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 : returnwc_ = self.wc[:1]for i in self.wc[1:]:if i == ALL and i == wc_[-1] : continuewc_.append(i)self.wc = wc_ #-----------------------------------------------------------------------------def matchExact(self,hd,pos = 0):if pos == len(self.wc) : return len(hd) == 0if self.wc[pos] == ALL :if pos + 1 == len(self.wc) : return Truevl = self.wc[pos + 1]cpos = -1while True:try : cpos = hd.index(vl,cpos + 1)except : return Falseif self.matchExact(hd[cpos + 1:],pos + 2) : return Trueelse:if len(hd) == 0 : return Falseif hd[0] != self.wc[pos] : return Falsereturn 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 : Trueelse:wc = WC(dt[0])#print wc.wcfor 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()#------------------------------------------------------------------------------- 推荐答案 你的目标是什么？你想学习或引起一场火焰战争？ ;-) 无论如何，我发现这个问题很有趣，所以你走了，这里是我的 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 myHaskell code. It could be shorter if I didn''t care about performance andwrote in specification style. It''s not very efficient either, because itwill generate all lists matching the given patterns. In GHCi you can test it by: 小修正：它应该是 generateNotMatching" ;. 祝你好运 Tomasz - 我是寻找至少在（Haskell || ML）&& （Linux || FreeBSD || math） 在波兰华沙工作 Minor correction: it should be "generateNotMatching". Best regardsTomasz --I am searching for programmers who are good at least in(Haskell || ML) && (Linux || FreeBSD || math)for work in Warsaw, Poland 这篇关于编程挑战：笛卡尔积中的通配符排除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！