Problema da soma de sub-ítens
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.
