Suma de subconjuntos. Enumeración. Subset sum. Enumeration.⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

[j2e2xae]

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.

Este problema puede abordarse en el contexto de las particiones de enteros, ver [suma_de_subconjuntos@j2e2xae] , pero en este caso vamos a solucionarlo en la forma de una recurrencia.

 

Recurrencia

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

 

⑴

 

 

 

⑵

 

 

⒜

 

 

 

 

 

⒝

 

 

 

 

⌘

 

       

Dados un conjunto de enteros positivos S = { a₁ , a₂ , ... a_m } y un entero positivo k,

             ∑ a   >   k
^m

Definimos una función F , con valor el número de subconjuntos de S con suma k .

F ( n₁ ,n₂ ...n_m ; k )

n_m < k  ∀ m

Si quitamos el elemento n_m , el subconjunto resultante da lugar a dos opciones para la realización de la suma, puedes elegir entre k  y  k − n_{m .}

F ( n₁ ,n₂ ...n_m ; k ) = F ( n₁ ,n₂ ...n_m-1 ; k − n_m ) + F ( n₁ ,n₂ ...n_m-1 ; k )

Hemos determinado una relación de recurrencia que nos permite resolver el problema de dimensión ( m, k ) con las soluciones en ( m  − 1,  k  − n _m  ) y ( m  − 1,  k  ).

Teniendo en cuenta las igualdades siguientes,

F (⋯ ; 0 ) = 0     

  F (⋯ k ⋯ ; k ) = 1 + F (⋯ ; k )

∑ S < k ⇒ F (S ; k ) = 0

∑ S = k ⇒ F (S ; k ) = 1

 

Podemos construir una solución recursiva ⒜ , ⒝
con casos base, ecuación ⒜ ,( ∅ , k ) y ( S , 0 ),
que ha de conservar las propiedades ⑴ y ⑵ .

Ordenar los elementos del conjunto de forma ascendente facilita la tarea de verificar las propiedades.

 

Ejemplo

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

       

S = { 1, 2, 3, 5, 10, 15, 20, 50 }, k = 73

∑ (1, 2, 3, 5, 10, 15, 20, 50) > 73

F (1, 2, 3, 5, 10, 15, 20, 50; 73) =
F₁ (1, 2, 3, 5, 10, 15, 20; 23) +
F₂ (1, 2, 3, 5, 10, 15, 20; 73)

F₁ : ∑ (1, 2, 3, 5, 10, 15, 20) > 23
F₁ (1, 2, 3, 5, 10, 15, 20; 23) =
F₁₁ (1, 2, 3, 5, 10, 15; 13) +
F₁₃ (1, 2, 3, 5, 10, 15; 23)

F₁₁ (1, 2, 3, 5, 10, 15; 13) = F₁₁ (1, 2, 3, 5, 10; 13)
∑ (1, 2, 3, 5, 10) > 13
F₁₁ (1, 2, 3, 5, 10; 13) =
F₂₁ (1, 2, 3, 5; 3) +
F₂₃ (1, 2, 3, 5; 13)

F₂₁ (1, 2, 3, 5; 3) = F₂₁ (1, 2, 3; 3)
F₂₁ (1, 2, 3; 3) = 1 + F₃₃ (1, 2; 3)
⋮
F₂₁ (1, 2, 3, 5; 3) = 2      
F₂₃ (1, 2, 3, 5; 13) = 0     
F₁₁ (1, 2, 3, 5, 10; 13) = 2   
F₁₃ (1, 2, 3, 5, 10, 15; 23) = 2 
F₁ (1, 2, 3, 5, 10, 15, 20; 23) = 4
F₂ (1, 2, 3, 5, 10, 15, 20; 73) = 0

F (1, 2, 3, 5, 10, 15, 20, 50; 73) = 4 + 0 = 4

 

∎

---

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.

This problem could be solved as an integer partitions one, see [subset_sum@j2e2xae], now we are solving it by a recurrence relation.

 

Recurrence

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

⑴

 

 

 

⑵

 

⒜

 

 

 

 

 

⒝

 

 

 

⌘

 

 

       

Given a positive integer set S = { a₁ , a₂ , ... a_m } and a positive integer k,

             ∑ a   >   k
^m

A function defined F , with value the number of S subsets that sum upto k .

F ( n₁ ,n₂ ...n_m ; k )

n_m < k  ∀ m

Drop n_m , remaining subset has two options to sum, k or ( k − n_m ),

F ( n₁ ,n₂ ...n_m ; k ) = F ( n₁ ,n₂ ...n_m-1 ; k − n_m ) + F ( n₁ ,n₂ ...n_m-1 ; k )

That is a recurrence relation that solves the problem ( m, k ) using solutions ( m  − 1,  k  − n _m  ) and ( m  − 1,  k  ).

Note the equalities,

F (⋯ ; 0 ) = 0     

  F (⋯ k ⋯ ; k ) = 1 + F (⋯ ; k )

∑ S < k ⇒ F (S ; k ) = 0

∑ S = k ⇒ F (S ; k ) = 1

 

We can build a recursive solution ⒜ and ⒝,
with base cases, ( ∅ , k ) and ( S , 0 ), in equation ⒜
and an invariant as properties ⑴ and ⑵ .

Ascendig ordering makes verifying invariant properties easier.

 

Example

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

       

S = { 1, 2, 3, 5, 10, 15, 20, 50 }, k = 73

∑ (1, 2, 3, 5, 10, 15, 20, 50) > 73

F (1, 2, 3, 5, 10, 15, 20, 50; 73) =
F₁ (1, 2, 3, 5, 10, 15, 20; 23) +
F₂ (1, 2, 3, 5, 10, 15, 20; 73)

F₁ : ∑ (1, 2, 3, 5, 10, 15, 20) > 23
F₁ (1, 2, 3, 5, 10, 15, 20; 23) =
F₁₁ (1, 2, 3, 5, 10, 15; 13) +
F₁₃ (1, 2, 3, 5, 10, 15; 23)

F₁₁ (1, 2, 3, 5, 10, 15; 13) = F₁₁ (1, 2, 3, 5, 10; 13)
∑ (1, 2, 3, 5, 10) > 13
F₁₁ (1, 2, 3, 5, 10; 13) =
F₂₁ (1, 2, 3, 5; 3) +
F₂₃ (1, 2, 3, 5; 13)

F₂₁ (1, 2, 3, 5; 3) = F₂₁ (1, 2, 3; 3)
F₂₁ (1, 2, 3; 3) = 1 + F₃₃ (1, 2; 3)
⋮
F₂₁ (1, 2, 3, 5; 3) = 2      
F₂₃ (1, 2, 3, 5; 13) = 0     
F₁₁ (1, 2, 3, 5, 10; 13) = 2   
F₁₃ (1, 2, 3, 5, 10, 15; 23) = 2 
F₁ (1, 2, 3, 5, 10, 15, 20; 23) = 4
F₂ (1, 2, 3, 5, 10, 15, 20; 73) = 0

F (1, 2, 3, 5, 10, 15, 20, 50; 73) = 4 + 0 = 4

 

∎

---

Media

Public domain, via Wikimedia Commons

   

       

Comments

[hivebuzz]

Congratulations @j2e2xae! You have completed the following achievement on the Hive blockchain And have been rewarded with New badge(s)

You distributed more than 500 upvotes. Your next target is to reach 600 upvotes.

_{You can view your badges on your board and compare yourself to others in the Ranking
If you no longer want to receive notifications, reply to this comment with the word STOP}