<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > Using Psyco this version is much faster, you can test it on your PC > compared to the other one (the whole running time, Psyco compilation > too): > Psyco is unable to speed up generator functions, so you have to return > true lists. > Giving the func to the permutation function, you can avoid lot of list > copying and unpacking. > > > try: > import psyco > psyco.full() > except ImportError: > pass > > d0, d1 = 1, 2 > > > def func(p): > a0,a1,a2,b0,b1,b2,c0,c1,c2 = p > # do application evaluation here > b1b2 = 10*b1+b2 > a1a2 = 10*a1+a2 > c1c2 = 10*c1+c2 > if d1*a0*b1b2*c1c2 + d1*b0*a1a2*c1c2 + d1*c0*a1a2*b1b2 \ > == d0*a1a2*b1b2*c1c2: > return sorted( [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] ) > else: > return None > > > def accepted_permutations(alist, func): > # func must return None for the unacceptable results > # Algoritm from Phillip Paul Fuchs, modified > result = [] > items = alist[:] > n = len(alist) > p = range(n+1) > i = 1 > r = func(alist) > if r is not None: result.append(r) > while i < n: > p[i] -= 1 > if i & 1: > j = p[i] > else: > j = 0 > alist[j], alist[i] = alist[i], alist[j] > r = func(alist) > if r is not None: result.append(r) > i = 1 > while p[i] == 0: > p[i] = i > i += 1 > return result > > > def main(): > result = [] > for aresult in accepted_permutations(range(1, 10), func): > if aresult not in result: > result.append(aresult) > [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] = aresult > print ' %0d %0d %0d %0d' % (a0, b0, c0, d0) > print '--- + --- + --- = ---' > print ' %0d%0d %0d%0d %0d%0d > %0d'%(a1,a2,b1,b2,c1,c2,d1) > print > > main() > > Bye, > bearophile >
Nice and neat. I guess what appeals to me is that this is essentially a brute force approach. Instead of a goal-seeking constraint solver, this just brute force tries every possible permutation. Of course, this breaks down quickly when the size of the input list grows large, but the OP was trying to work with permutations of the digits 1-9 using an unwieldy nesting of for loops and set manipulations. Using permutations is no more or less smart of an algorithm than in the original post, it just cleans up the for loops and the set arithmetic. For example, for all the complexity in writing Sudoku solvers, there are fewer than 3.3 million possible permutations of 9 rows of the digits 1-9, and far fewer permutations that match the additional column and box constraints. Why not just compute the set of valid solutions, and compare an input mask with these? -- Paul -- http://mail.python.org/mailman/listinfo/python-list
