Suma  de  subconjuntos. Subset  sum.⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

avatar
(Edited)
EspañolEnglish

Dado un conjunto arbitrario de enteros,

¿ Existe un subconjunto cuya suma sea exactamente un valor dado ?

 

 

 

 

 

 

 

 

 

 

   

 

+

 

 

 

 

 

 

 

 

       


En esta ocasión nos vamos a ocupar de una versión del problema enunciado, restringiendo el conjunto de partida a los enteros positivos.

Enumerar las particiones de un entero positivo parece una buena estrategia en la búsqueda de una solución, los elementos de una partición de un entero n suman exactamente n .

El número de particiones de un entero n , coincide con el coeficiente de x n en el desarrollo de la expresión,

( 1 − x ) -1 ( 1 − x 2 ) -1 ( 1 − x 3 ) -1 ...

∵  ( 1 − x r ) -1 = 1 + x r + x 2r + ... + x n r + ...

Podemos expresar estas relaciones como un producto de binomios,

( 1 − x r ) -1 = ( 1 + x r )( 1 + x 2r ) ... ( 1 + x 2n r ) ...

Esta última expresión será la herramienta que utilizaremos para resolver el problema de la suma de subconjuntos .

 

Existencia

 

 

 

 

 

   

 

 

 

 

 

       

Determinar la existencia de solución se reduce a calcular el coeficiente de x n en el producto de binomios,

{ 5, 8, 9, 13, 17 },  n = 27

( 1 + x 5 )( 1 + x 8 )( 1 + x 9 )( 1 + x 13 )( 1 + x 17 )

... + 3 x 30 + x 27 + 2 x 26 + ...

El coeficiente de x 27 es la unidad, de forma que existe una solución.

 

Cardinalidad

 

 

 

 

 

   

 

 

 

#

 

 

       

Nos preguntamos ahora sobre el número de elementos de cada subconjunto solución.
Utilizaremos una variable auxiliar que, a modo de testigo , llevará la cuenta de las cardinalidades.

( 1 + ax 5 )( 1 + ax 8 )( 1 + ax 9 )( 1 + ax 13 )( 1 + ax 17 )

... + ( 2a 3 + a 2) x 30 + a 3 x 27 + ( a 3 + a 2) x 26 + ...

El coeficiente de x 27 contiene al testigo a , con exponente tres, cardinalidad del único subconjunto solución.

 

Valores

 

 

 

   

 

 

{ }

 

       

Vamos a determinar los valores de cada subconjunto solución, para ello etiquetaremos cada variable testigo con un subíndice adecuado.

( 1 + a5 x 5 )( 1 + a8 x 8 )( 1 + a9 x 9 )( 1 + a13 x 13 )( 1 + a17 x 17 )

... + a 5 a 9 a 13 x 27 + ...

Subconjunto solución, { 5, 9, 13 }.

 


EnglishEspañol

An integer set given,

Is there any subset that sums precisely upto other integer ?

 

 

 

 

 

 

 

 

 

 

   

 

+

 

 

 

 

 

 

 

 

       


We restrict our attention to a variant of this problem involving positive integers only.

Enumerating integer partitions could be a technique to solving this problem, integers in a partition of n sum upto n .

The number of partitions of an integer n match the coefficient of x n in the expansion of expression,

( 1 − x ) -1 ( 1 − x 2 ) -1 ( 1 − x 3 ) -1 ...

∵  ( 1 − x r ) -1 = 1 + x r + x 2r + ... + x n r + ...

We can transform this into a product of binomials,

( 1 − x r ) -1 = ( 1 + x r )( 1 + x 2r ) ... ( 1 + x 2n r ) ...

This last expression will be the tool that we are using to solve the subset sum problem.

 

Existence

 

 

 

 

 

   

 

 

 

 

 

       

To decide if there is a solution mere calculate the coefficient of x n in the product of binomials,

{ 5, 8, 9, 13, 17 },  n = 27

( 1 + x 5 )( 1 + x 8 )( 1 + x 9 )( 1 + x 13 )( 1 + x 17 )

... + 3 x 30 + x 27 + 2 x 26 + ...

Unity is the coefficient of x 27 so there is an only one solution.

 

Cardinality

 

 

 

 

 

   

 

 

 

#

 

 

       

We are asking now about number of integers in solution's subsets.
Using an auxiliar variable, like a marker , we can count solution subset's elements.

( 1 + ax 5 )( 1 + ax 8 )( 1 + ax 9 )( 1 + ax 13 )( 1 + ax 17 )

... + ( 2a 3 + a 2) x 30 + a 3 x 27 + ( a 3 + a 2) x 26 + ...

x 27 has as coefficient a with power index three, cardinality of the solution subset.

 

Value

 

 

 

   

 

 

{ }

 

       

Members of each solution subset can be calculated tagging the auxiliary variables with a proper subindex.

( 1 + a5 x 5 )( 1 + a8 x 8 )( 1 + a9 x 9 )( 1 + a13 x 13 )( 1 + a17 x 17 )

... + a 5 a 9 a 13 x 27 + ...

Solution subset, { 5, 9, 13 }.

 


Media Public domain, via Wikimedia Commons


0
0
0.000
2 comments
avatar

Que olvidado tenia este tema que vi en la facultad de ingeniería , buen post!

0
0
0.000