Decided I may as well post my other solution while I'm at it. The neat trick here is redefining the add, mul, etc. functions so that they raise exceptions for example if x>y then add(x,y) raises an exception which is handled by the search algorithm to mean don't continue that computation - this stops you from having to evaluate x+y AND y+x, etc.
sub = lambda x,y:x-y def add(x,y): if x<=y: return x+y raise ValueError def mul(x,y): if x<=y or x==1 or y==1: return x*y raise ValueError def div(x,y): if not y or x%y or y==1: raise ValueError return x/y add.disp = '+' mul.disp = '*' sub.disp = '-' div.disp = '/' standard_ops = [ add, sub, mul, div ] def strexpression(e): if len(e)==3: return '('+strexpression(e[1])+e[0].disp+strexpression(e[2]) +')' elif len(e)==1: return str(e[0]) # I don't like this function, it's nice and short but is it clear # what it's doing just from looking at it? def expressions(sources,ops=standard_ops,minremsources=0): for i in range(len(sources)): yield ([sources[i]],sources[:i]+sources[i+1:],sources[i]) if len(sources)>=2+minremsources: for e1, rs1, v1 in expressions(sources,ops,minremsources+1): for e2, rs2, v2 in expressions(rs1,ops,minremsources): for o in ops: try: yield ([o,e1,e2],rs2,o(v1,v2)) except ValueError: pass def findfirsttarget(target,sources,ops=standard_ops): for e,s,v in expressions(sources,ops): if v==target: return strexpression(e) return None print findfirsttarget(923,[7,8,50,8,1,3]) gives: ((7*(((8*50)-1)/3))-8) Dan Goodman -- http://mail.python.org/mailman/listinfo/python-list