Results 1 to 2 of 2

Thread: Sum Subsets

  1. #1
    Sep 2012

    Sum Subsets

    Hi everyone, first time on this forum and I'm thrilled. I was wondering if anyone could perhaps show me where I can find an article, formula, book, etc, that tells me what I want to find below.

    You have a number n and a list of numbers. I want to generate all the different combinations from the list that add up the n.

    n = 4;
    list = [1,2]

    Combination 1: 1 + 1 + 1 + 1 = 4
    Combination 2: 1 + 1 + 2 = 4
    Combination 3: 2 + 2 = 4

    There are 3 different combinations that sum up to 4 from the given list.

    n = 6
    list = [1,3,6]

    Combination 1: 1+1+1+1+1+1 = 6
    Combination 2: 1+1+1+3 = 6
    Combination 3: 3+3 = 6
    Combination 4: 6=6

    There are 4 different combinations that sum up to 6 from the given list.

    Is there an algorithm or something that I can use in a java program that will accomplish this?

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Sep 2012
    Washington DC USA

    Re: Sum Subsets

    A desired combination isn't a set, because you need to include repetition. Instead call it a finite sequence in A = Seq(A).
    We won't care about the ordering, even though calling it a sequence does naturally includes ordering. No problem.
    If a and b are such finite sequences in A, call a*b the combined sequence of "first do a, then do b"
    Ex: Let A = {1, 2, 5} and a,b in Seq(A) given by a(1) = 1, a(2) = 1, a(3) = 5, and b(1) = 5, b(2) = 2.
    Then a*b = Seq(A) is given by (a*b)(1) = 1, (a*b)(2) = 1, (a*b)(3) = 5, and (a*b)(4) = 5, (a*b)(5) = 2.
    For completeness, assume 0 is not allowed in A, and "{after the sequence is done", all the sequence values are 0.
    Then a*b is re-defined by "b starts replacing the 1st occurance of 0 in a"
    This is all mumbo-mubo, just for precision's sake.
    It's really just that a is a finite "subset" of A, except repetition is allowed. And a*b is just "a union b", except tracking repetitions.

    Definition: If $\displaystyle A \subset \mathbb{Z}^+$, define $\displaystyle Seq(A) = \{ a:\mathbb{Z}^+ \rightarrow A \cup \{0\} | \exists k \in \mathbb{Z}^+ \ni a(i) \in A \forall i < k$, and $\displaystyle a(i) = 0 \forall i \ni i \ge k \}$.

    Definition: Call that special k in the above definition $\displaystyle len(a)$ (length of a).

    Definition: If $\displaystyle a, b \in Seq(A)$, define $\displaystyle a*b \in Seq(A)$ by $\displaystyle (a*b)(k) = a(k)$ for $\displaystyle k < len(a)$, and $\displaystyle (a*b)(k) = b(k-len(a)+1)$ for $\displaystyle k \ge len(a)$.

    Definition: If $\displaystyle a \in Seq(A), B \subset Seq(A)$, define $\displaystyle a*B \subset Seq(A)$ by $\displaystyle a*B = \{a*b | b \in B \}$. Similarly for $\displaystyle B*a$.

    Define: $\displaystyle a * \emptyset = \emptyset$ for all $\displaystyle a \in Seq(A)$.

    Definition: If $\displaystyle k \in A$, define $\displaystyle c_k \in Seq(A)$ by $\displaystyle c_k(1) = k$, and $\displaystyle c_k(i) = 0$ for $\displaystyle i >1$.

    Definition: Let $\displaystyle Combination(n, A) = \{ a \in Seq(A) | \Sigma_{i=1}^{\infty} a(i) = n \}$.

    All that overhead crap is for a very simple recursive algorithm:

    $\displaystyle Combination(n, A) = \cup_{k \in A, k<=n} (c_k * Combination(n-k, A))$


    The meaning of that is "the combinations of A that sum to n" is the union over every k in A of "the combinations of A that sum to n-k, and then include k".
    Last edited by johnsomeone; Sep 24th 2012 at 12:31 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sum Subsets
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Sep 28th 2012, 07:36 AM
  2. Subsets
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Dec 29th 2010, 10:33 AM
  3. subsets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 1st 2010, 09:52 AM
  4. how many subsets?
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Mar 21st 2010, 12:21 PM
  5. subsets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 7th 2009, 01:24 PM

Search Tags

/mathhelpforum @mathhelpforum