Suma de subconjuntos. Subset sum.⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
| Español | English |
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 }.
∎
| English | Españ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
.svg){kind=link}
Que olvidado tenia este tema que vi en la facultad de ingeniería , buen post!
Gracias por comentar