Problema de suma de subconjuntos

8 minutos de lectura

avatar de usuario
alberto leal

Recientemente me interesé en el problema de la suma de subconjuntos, que consiste en encontrar un subconjunto de suma cero en un superconjunto. Encontré algunas soluciones en SO, además, me encontré con un particular solución que utiliza el enfoque de programación dinámica. Traduje su solución en python en base a sus descripciones cualitativas. Estoy tratando de optimizar esto para listas más grandes que consumen mucha memoria. ¿Alguien puede recomendar optimizaciones u otras técnicas para resolver este problema en particular? Aquí está mi intento en Python:

import random
from time import time
from itertools import product

time0 = time()

# create a zero matrix of size a (row), b(col)
def create_zero_matrix(a,b):
    return [[0]*b for x in xrange(a)]

# generate a list of size num with random integers with an upper and lower bound
def random_ints(num, lower=-1000, upper=1000):
    return [random.randrange(lower,upper+1) for i in range(num)]

# split a list up into N and P where N be the sum of the negative values and P the sum of the positive values.
# 0 does not count because of additive identity
def split_sum(A):
    N_list = []
    P_list = []
    for x in A:
        if x < 0:
            N_list.append(x)
        elif x > 0:
            P_list.append(x)
    return [sum(N_list), sum(P_list)]

# since the column indexes are in the range from 0 to P - N
# we would like to retrieve them based on the index in the range N to P
# n := row, m := col
def get_element(table, n, m, N):
    if n < 0:
        return 0
    try:
        return table[n][m - N]
    except:
        return 0

# same definition as above
def set_element(table, n, m, N, value):
    table[n][m - N] = value

# input array
#A = [1, -3, 2, 4]
A = random_ints(200)

[N, P] = split_sum(A)

# create a zero matrix of size m (row) by n (col)
#
# m := the number of elements in A
# n := P - N + 1 (by definition N <= s <= P)
#
# each element in the matrix will be a value of either 0 (false) or 1 (true)
m = len(A)
n = P - N + 1;
table = create_zero_matrix(m, n)

# set first element in index (0, A[0]) to be true
# Definition: Q(1,s) := (x1 == s). Note that index starts at 0 instead of 1.
set_element(table, 0, A[0], N, 1)

# iterate through each table element
#for i in xrange(1, m): #row
#    for s in xrange(N, P + 1): #col
for i, s in product(xrange(1, m), xrange(N, P + 1)):
    if get_element(table, i - 1, s, N) or A[i] == s or get_element(table, i - 1, s - A[i], N):
        #set_element(table, i, s, N, 1)
        table[i][s - N] = 1

# find zero-sum subset solution
s = 0
solution = []
for i in reversed(xrange(0, m)):
    if get_element(table, i - 1, s, N) == 0 and get_element(table, i, s, N) == 1:
        s = s - A[i]
        solution.append(A[i])

print "Solution: ",solution

time1 = time()

print "Time execution: ", time1 - time0

  • Podría estar pensando en usar pytables para almacenar listas enormes.

    –Alberto Leal

    16 de mayo de 2011 a las 4:04

  • yo sugeriría numpy para un menor uso de memoria

    –Antony Hatchkins

    16 de mayo de 2011 a las 6:02

  • Intenté usar numpy.array(), pero esto casi duplicó la velocidad de ejecución 🙂

    – lugares

    16 de mayo de 2011 a las 6:15

  • Creo que el problema que está tratando de resolver es NP-Complete, por lo que incluso si logra optimizar marginalmente este código (que ya parece estar bien optimizado), el tiempo de ejecución (y quizás el consumo de memoria) explotará con listas más grandes …

    – phynfo

    16 de mayo de 2011 a las 7:47

  • @plaes: traté de usar la matriz de numpy, pero tal como dijiste, aumentó la velocidad de ejecución.

    –Alberto Leal

    19 de mayo de 2011 a las 7:24

No estoy muy seguro de si su solución es exacta o una PTA (aproximación de tiempo poli).

Pero, como alguien señaló, este problema es de hecho NP-Completo.

Es decir, cada algoritmo conocido (exacto) tiene un comportamiento de tiempo exponencial en el tamaño de la entrada.

Es decir, si puede procesar 1 operación en 0,01 nanosegundos, para obtener una lista de 59 elementos, necesitará:

2^59 ops -->     2^59     seconds -->     2^26      years -->      1 year
            --------------           ---------------
            10.000.000.000           3600 x 24 x 365

Puede encontrar heurísticas, que le dan la OPORTUNIDAD de encontrar una solución exacta en tiempo polinomial.

Por otro lado, si restringes el problema (a otro) usando límites para los valores de los números en el conjunto, entonces la complejidad del problema se reduce al tiempo polinomial. Pero incluso entonces, el espacio de memoria consumido será un polinomio de orden MUY alto.
La memoria consumida será mucho mayor que los pocos gigabytes que tiene en la memoria. E incluso mucho mayor que los pocos terabytes de su disco duro.

(Eso es para valores pequeños del límite para el valor de los elementos en el conjunto)

Puede ser que este sea el caso de su algoritmo de programación dinámica.

Me pareció que estaba usando un límite de 1000 al construir su matriz de inicialización.

Puedes probar con un límite más pequeño. Eso es… si su entrada consiste consistentemente en valores pequeños.

¡Buena suerte!

A alguien en Hacker News se le ocurrió la siguiente solución al problema, que me gustó bastante. Simplemente sucede que está en python :):

def subset_summing_to_zero (activities):
  subsets = {0: []}
  for (activity, cost) in activities.iteritems():
      old_subsets = subsets
      subsets = {}
      for (prev_sum, subset) in old_subsets.iteritems():
          subsets[prev_sum] = subset
          new_sum = prev_sum + cost
          new_subset = subset + [activity]
          if 0 == new_sum:
              new_subset.sort()
              return new_subset
          else:
              subsets[new_sum] = new_subset
  return []

Pasé unos minutos con él y funcionó muy bien.

  • Hola skorks, también encontré esta solución en las noticias de hackers. La persona que publicó esa solución dijo que podía hacerla más eficiente. ¿Sabes cómo se podría hacer esto más eficiente?

    –Alberto Leal

    11 de junio de 2011 a las 9:13

  • No he jugado con él lo suficiente como para intentar optimizarlo, por lo que realmente no puede ser de mucha ayuda para ti. Sin embargo, no importa lo que haga, si su conjunto de entrada es lo suficientemente grande y su rango de números es lo suficientemente amplio, eventualmente se atascará.

    – zorrillos

    21 de junio de 2011 a las 13:42

avatar de usuario
mitchus

Hay disponible un artículo interesante sobre cómo optimizar el código de python. aquí. Básicamente, el resultado principal es que debe alinear sus bucles frecuentes, por lo que en su caso esto significaría que en lugar de llamar get_element dos veces por ciclo, coloque el código real de esa función dentro del ciclo para evitar la sobrecarga de la llamada a la función.

¡Espero que ayude! Salud

avatar de usuario
luka rahne

primera captura de ojo

def split_sum(A):
  N_list = 0
  P_list = 0
  for x in A:
    if x < 0:
        N_list+=x
    elif x > 0:
        P_list+=x
  return [N_list, P_list]

Algunos consejos:

  1. Intente usar la lista 1D y use bitarray para reducir la huella de memoria al mínimo (http://pypi.python.org/pypi/bitarray) para que solo cambie la función get/set. Esto debería reducir su huella de memoria en al menos 64 (el número entero en la lista es un puntero a tipo entero, por lo que puede ser un factor 3 * 32)

  2. Evite usar try – catch, pero descubra los rangos adecuados al principio, es posible que descubra que ganará una gran velocidad.

El siguiente código funciona para Python 3.3+, he usado el módulo itertools en Python que tiene algunos métodos excelentes para usar.

from itertools import chain, combinations
def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

nums = input("Enter the Elements").strip().split() inputSum = int(input("Enter the Sum You want"))

for i, combo in enumerate(powerset(nums), 1): sum = 0 for num in combo: sum += int(num) if sum == inputSum: print(combo)

La salida de entrada es la siguiente:

Enter the Elements 1 2 3 4
Enter the Sum You want 5
('1', '4')
('2', '3')

avatar de usuario
eric aya

Simplemente cambie los valores en su conjunto w y, en consecuencia, haga una matriz x tan grande como la longitud de w, luego pase el último valor en la función subsetsum como la suma para la que desea subconjuntos y ya habrá terminado (si desea verificar por dando sus propios valores).

def subsetsum(cs,k,r,x,w,d):
    x[k]=1
    if(cs+w[k]==d):
        for i in range(0,k+1):

            if x[i]==1:
                print (w[i],end=" ")
        print()

    elif cs+w[k]+w[k+1]<=d :
        subsetsum(cs+w[k],k+1,r-w[k],x,w,d)

    if((cs +r-w[k]>=d) and (cs+w[k]<=d)) :
        x[k]=0
        subsetsum(cs,k+1,r-w[k],x,w,d)
#driver for the above code
w=[2,3,4,5,0]
x=[0,0,0,0,0]

subsetsum(0,0,sum(w),x,w,7)     

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad