El problema de la suma de los subconjuntos

En esta ocasión vamos a hablar de un problema que es muy sencillito de entender, pero que resulta muy complicado resolver. Lo normal en informática, vamos. Se trata del problema de la suma de los subconjuntos: dado un conjunto de números enteros tenemos que encontrar un subconjunto cuya suma sea 0, en el caso de que dicho subconjunto exista. Por ejemplo, si tenemos el conjunto formado por los números {−7, −3, −2, 5, 8}, tendríamos que devolver {−3, −2, 5}, ya que éstos suman 0. El problema de la suma de subconjuntos es importante porque se trata de un problema NP-Completo. Es decir, es muy fácil verificar si una solución es correcta (tan sólo hay que sumar los valores y ver si da 0), pero al día de hoy no se conoce ningún algoritmo que lo resuelva de manera eficiente (en un tiempo que sea del orden de un polinomio).

En esta ocasión vamos a resolver el problema utilizando la fuerza bruta, y mediante un algoritmo basado en la programación funcional, porque no sólo de algoritmos imperativos vive el hombre. Y más concretamente, utilizando el entorno de cálculo estadístico R, que para esto de manejar conjuntos de datos se apaña muy bien.

En primer lugar vamos a definir nuestro conjunto de enteros:

c <- c(−7, −3, −2, 5, 8, 9, 15, 6, 4, -11, -13, -1, 1, -14, 2, 3, 5, -14)

En este caso, formado por 18 enteros. No pongáis muchos más, porque el algoritmo de la fuerza bruta que vamos a utilizar tiene un tiempo de ejecución del orden de 2^n, donde n es el número de enteros, y con 18 ya nos llevará un rato.

A continuación calculamos todos los subconjuntos posibles de nuestro conjunto inicial, excepto el conjunto vacío, por razones obvias (en esta entrada expliqué un algoritmo muy bonito que resuelve cómo hacer esto):

combinaciones <- lapply(1:length(c), function(x) combn(c, x))

Para cada uno de estos subconjuntos calculamos su suma:

suma <- lapply(1:length(combinaciones), function(x) apply(combinaciones[[x]], 2, sum))

Y de estas sumas nos quedamos aquellas que valen 0:

cierto <- lapply(1:length(suma), function(x) ifelse(suma[[x]] == 0, TRUE, FALSE))

A continuación miramos qué subconjunto es el que corresponde a las sumas que valen 0:

soluciones <- lapply(1:length(combinaciones), function(x) combinaciones[[x]][,cierto[[x]]])

Y finalmente, limpiamos un poquito el resultado para que quede mono:

soluciones[sapply(soluciones, function(x) length(x)==0)] <- NULL

En futuras entradas veremos otros algoritmos más eficientes que la fuerza bruta para resolver este problema.

Como ejercicio dejo propuesto escribir un programa que nos diga si dado un conjunto es posible dividirlo en dos subconjuntos que sumen lo mismo. Y para aquellos lectores a los que no les guste la programación funcional, les dejo como ejercicio que escriban el mismo algoritmo utilizando un lenguaje imperativo, por ejemplo, C. ¡Ánimo!