Results 1 to 2 of 2

Math Help - Sum Subsets

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    LA
    Posts
    2

    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.
    Example.

    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
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    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 A \subset \mathbb{Z}^+, define Seq(A) = \{ a:\mathbb{Z}^+ \rightarrow A \cup \{0\} | \exists k \in \mathbb{Z}^+ \ni a(i) \in A \forall i < k, and a(i) = 0 \forall i \ni i \ge k \}.

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

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

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

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

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

    Definition: Let 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:

    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; September 24th 2012 at 01: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: September 28th 2012, 08:36 AM
  2. Subsets
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: December 29th 2010, 11:33 AM
  3. subsets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2010, 10:52 AM
  4. how many subsets?
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: March 21st 2010, 01:21 PM
  5. subsets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2009, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum