Problema da soma de sub-ítens

Posted on 19 \d\e janeiro \d\e 2010. Filed under: python | Tags:, , , , , , , , , |

Estes dias estava desenvolvendo um programa de conciliação contábil quando me deparei com um problema de programação, no trampo. Passei o programa no canal #python-br e estamos tentando resolvê-lo da forma que tenha mais performance.

Achei muito interessante o fato de conseguir envolver a todos, muita gente está tentando escrever o algoritmo.

O problema consiste em fazer um algoritmo que ao receber uma lista de números inteiros, retorne uma sublista cuja soma é zero.

Porém, tem os seguintes modificadores:

  • Caso não exista nenhuma sublista que alcance zero, a lista vazia deverá ser retornada.
  • Caso exista mais de uma sublista que some zero, o algoritmo deve encontrar aquela que tem o maior valor absoluto, ou seja, o maior valor desconsiderando o sinal (módulo).
  • Em caso de empate, qualquer uma das combinações pode ser retornada.

Nada como alguns exemplos para entender melhor:

  • Para a lista [-5, -3, 10, 16] não tem nenhuma sublista que dê zero, então o algoritmo deve retornar a lista vazia []
  • No caso da lista [-5, -3, 3, 10] o algoritmo deve calcular a sublista [-3, 3] (cuja soma dá 0).
  • Porém, se a lista é [-15, -3, 3, 18] o algortmo tem duas possibilidades cuja soma é zero:
    • retornar [-3, 3] (soma 0)
    • retornar [-15, -3, 18] (soma 0)
  • Quando isso ocorrer, o algoritmo deve estar montado de forma a retornar a sublista com maior valor absoluto, ou seja, [-15, -3, 18] (soma absoluta 36).

Após intensiva pesquisa, encontrei isto na wikipedia. O problema é da classe NP-Hard, e não existe solução linear. Porém com uma linguagem dinâmica, é possível fazer soluções pseudo-polinomiais.

O que estou procurando é justamente este algoritmo otimizado.

Resolvi desenvolver primeiramente o programa de referência. Este programa encontra a solução do problema através da força bruta, ou seja, gera todas as possibilidades de combinações existentes, soma cada uma pra encontrar as combinações cuja soma é zero, e depois verifica qual delas é a que tem maior valor absoluto. A resposta deste código sempre está correta, porém, o tempo para gerar todas as possibilidades é quadrático e dobra a cada novo ítem acrescentado na lista.

Aqui está o programa de referência:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Copyright © 2010 Clóvis Fabrício Costa
# Licensed under GPL version 3.0 or higher 

from itertools import chain, combinations

def acha_combinacao(itens):
    """
    Função que resolve o problema "subset sum" através da geração de todas
    as possibilidades.
    
    Passe uma lista de números inteiros, e a função retornará uma sublista
    cuja soma é zero. 
    
    Caso não exista nenhuma sublista que alcance zero, a lista vazia será
    retornada.
    
    Caso exista mais de uma sublista que tem zero, o algoritmo deve encontrar
    aquela que tem o maior valor absoluto, ou seja, o maior valor 
    desconsiderando o sinal (módulo).
    
    Em caso de empate, qualquer uma das combinações pode ser retornada.
    """
    # gera todas as combinações possíveis
    todas_combs = chain.from_iterable(combinations(itens, n+1)
                                   for n in xrange(len(itens)))
    # procura a maior
    maior_comb = []
    maior_somaabs = 0
    for comb in todas_combs:
        if sum(comb) != 0:
            continue # Combinação não dá zero, pulando.
        somaabs = sum([abs(item) for item in comb])
        if somaabs > maior_somaabs:
            maior_comb = comb
            maior_somaabs = somaabs
    return maior_comb

Para quem quiser tentar fazer o seu algoritmo, estou disponibilizando em meu repositório o programa de referência acima, todas as minhas tentativas até agora, um arquivo de dados contendo números para teste com a respectiva resposta correta, e um programa que lê este arquivo de dados e testa a sua função automaticamente. Desta forma fica fácil achar os problemas do código.

A versão disponibilizada no repositório é compatível com versões do python < 2.6 (o código acima não é).

O repositório está hospedado no bitbucket, e pode ser baixado utilizando o mercurial, com o seguinte comando:

hg clone http://bitbucket.org/nosklo/subset_sum

Para testar seu código, coloque seu arquivo contendo o código na mesma pasta onde você baixou o repositório acima e use o seguinte modelo:

1
2
import referencia
referencia.teste(sua_funcao)

Isso é o suficiente. A sua função será testada com todos os dados de teste que gerei, e vai mostrar qualquer erro encontrado nos resultados.

Qualquer dúvida, estou no canal #python-br da freenode. Muito obrigado a todos que estão ajudando a encontrar este algoritmo.

Anúncios

Make a Comment

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

  • Blog Stats

    • 4,163 hits
  • contribua!

Liked it here?
Why not try sites on the blogroll...