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