some OT: how to solve this kind of problem in our program?

[Paul McGuire]

"oyster" <lepto.python at gmail.com> wrote in message 
news:mailman.1995.1166935152.32031.python-list at python.org...
> 1. first of all, what is the English jargon (Optimize? But I think
> this is not a very good keyword :( )for this problem? So I can use it
> to search on the internet
> 2. is there any free/open lib for this?
> 3. I know for some questions(case 1, case 2, and sudoku), we can use
> bundles of "FOR...NEXT" loop to program. however I think it is clumsy
> and inconvenient, especially when there is many vars
> 4. I don't know how to deal with case 3 and case 4
>
>
> case:
> 1. choose x0~x9 from 1~9, and must use all of 1~9, let
> x0/(10*x1+x2)+x3/(10*x4+x5)+x6/(10*x7+x8)=1/2
>

Since you are working with permutations of [1..9], here is a general 
framework for problems using those permutations - put your problem 
definition in the function func, which is successively passed each of the 
362880 permutations of the numbers 1-9.  On my system, your original code 
ran in about 11 seconds, and after factoring out invariants, got down to 
about 1.8 seconds.  This little framework takes about 4.5 seconds, but with 
psyco, cuts down to about 1.3 seconds.

-- Paul


import time
try:
  import psyco
  psyco.full()
except:
  pass

def prod(lst):
    return reduce(lambda a,b:a*b,lst,1)

def perms(setSize, sampleSize):
    return prod(xrange(setSize-sampleSize+1,setSize+1))

def permutation(k, s):
    fact = 1
    s = s[:]
    for j in xrange( 2, len(s)+1):
        fact = fact * (j-1)
        idx1 = j - ((k / fact) % j)-1
        idx2 = j-1
        s[idx1],s[idx2] = s[idx2],s[idx1]
    return s

def permutations(s,sampleSize=None):
    if sampleSize is None:
        sampleSize = len(s)
    k = perms(len(s),sampleSize)
    for i in xrange(k):
        yield permutation(i,s)

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

st = time.time()
result = []
for p in permutations(range(1,10)):
    aresult = func(p)
    if aresult is not None and aresult not in result:
        result.append(aresult)

et=time.time()
print 'time elapsed: %.4f s' % (et-st)
for [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] in result:
  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