Sobre o Problema Da Soma De Sub-Ítens Do noskleta

Referente ao post do nosklo http://pythonlog.wordpress.com/2010/01/19/problema-da-soma-de-sub-itens/ O código a seguir consegue executar todos os testes de dados_teste.txt em menos de 2 segundos em um processador x4 955 overclock 4ghz

from itertools import chain, combinations
       
itens = range(-2000, 1, 1) + range(1,10, 3)
a = sorted([i for i in itens if i > 0], reverse=True)
b =  sorted([i for i in itens if i < 0], reverse=True)
found = False
totalB = abs(sum(b))
 
if sum(a) < totalB:
    a, b = b, a
    totalB = abs(sum(b))            
   
       
if b != [] or a != []:
  
    if len(a) < 30:
 
        for i in chain.from_iterable(combinations(a, n+1)
                           for n in xrange(len(b),0,-1)):
        
            if abs(sum(i)) - totalB == 0:
                currentList = a+b
                sublist =  list(i)+b
                absoluteValue= (abs(sum(i)) + totalB)
                print  "com %s retornou %s Cujo o Valor absoluto é: %s  " \
                                  % (currentList,  sublist,  absoluteValue)
                found = True
                break
         
    else:
 
        loop = True
        size = len(a)
         
        while loop and size >= 2:       
   
            for i in chain.from_iterable(combinations(a, n+1)
                                 for n in xrange(size,0,-1)):
   
                if sum(abs(j) for j in i) >=  totalB:
                    size-=1
                    break
                else:
                    loop = False
                break
             
        for i in chain.from_iterable(combinations(a, n+1)
                                  for n in xrange(size,0,-1)):
        
            if abs(sum(i)) - totalB == 0:
                currentList = a+b
                sublist =  list(i)+b
                absoluteValue= (abs(sum(i)) + totalB)
                print  "com %s retornou %s Cujo o Valor absoluto é: %s  " \
                          % (currentList,  sublist,  absoluteValue)
                found = True
                break

    if not found:
        for i in chain.from_iterable(combinations(itens, n+1)
                         for n in xrange(len(itens), 0, -1)):
            if abs(sum(i)) == 0:
                currentList = itens
                sublist =  list(i)
                absoluteValue= sum( abs(j) for j in i )
                print  "com %s retornou %s Cujo o Valor absoluto é: %s  " \
                                  % (currentList,  sublist,  absoluteValue)
                found = True
                break
        
   
    if not found:     
        print "%s Nenhuma sublista" % itens

Agistech.com.br