Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm trying to figure out how the combos work (I think this is a form of number theory).

For example, for a sum of 10 and using a universe of [4, 2, 1], I get (I'm showing how I perceive the breakdown):

2 * 4 +  1 * 2 +  0 * 1 = 4 + 4 + 2
2 * 4 +  0 * 2 +  2 * 1 = 4 + 4 + 1 + 1
1 * 4 +  3 * 2 +  0 * 1 = 4 + 2 + 2 + 2
1 * 4 +  2 * 2 +  2 * 1 = 4 + 2 + 2 + 1 + 1
1 * 4 +  1 * 2 +  4 * 1 = 4 + 2 + 1 + 1 + 1 + 1
1 * 4 +  0 * 2 +  6 * 1 = 4 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 +  5 * 2 +  0 * 1 = 2 + 2 + 2 + 2 + 2
0 * 4 +  4 * 2 +  2 * 1 = 2 + 2 + 2 + 2 + 1 + 1
0 * 4 +  3 * 2 +  4 * 1 = 2 + 2 + 2 + 1 + 1 + 1 + 1
0 * 4 +  2 * 2 +  6 * 1 = 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 +  1 * 2 +  8 * 1 = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 +  0 * 2 + 10 * 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

So as the numbers get larger, I am having problems scaling it (if I have a sum of 1000 with 30 variables, it take forever). So looking at the problem like I have above, I thought I could break down the result based. So what I do is take the universe list [4,2,1] and go through the list and see how many of the previous numbers takes to make that number. Here's an example:

2 [[1, 1]]
4 [[2, 2]]
4 [[2, 2]]

What that means is 1+1=2, 2+2=4, so I can use that table to break down the first highest result (4+4+2... I look up the table and see that 2 = 1+1 so I replace that, then go back to the first highest result and then lookup the breakdown of the second number, etc.). I'm not sure but I believe this can scale because I can split the calculation and lookups over separate CPU/systems/clusters/etc..

There's probably many logical flaws, but the one I noticed right now is what if the number is a prime number or doesn't break down into the last highest number? Say my universe changes from [4,2,1] to [4,3,2,1]... because the highest match is still 4+4+2, the 3 will get missed totally as a solution.

So I'm wondering how I can mathematically deal with prime numbers (I have a function to identify them)? Also what is the correct logic if I have numbers that don't divide cleanly into each other? (universe of [6,4,2,1] breaks down also). In the past I brute forced this (try all until successful) the problem is, if I can't break down the problem into smaller math problems than I can't scale it. I think this can be done because I can scale it (on a small scale :-), but dealing with specific numbers are the problem (prime and I guess numbers that are the opposite of the sum odd or even).

Sorry for the long question and again, sorry if this is not appropriate for this Q/A but any suggestion or advice would helpful.

share|improve this question
1  
Let me clarify your question: you want to write a computer program which, given a positive integer $n$ and a list of positive integers $S = \{m_1, m_2, \ldots m_k\}$ as input, produces a list of every way of writing the number $n$ as a sum of elements of $S$? –  Daniel McLaury Sep 25 '11 at 2:20
    
@user3296 yes thats correct. I wrote the program but it didn't scale so I thought I'd break it down by values of the highest combo. Now I have the main algo as the base case but trying to figure out how to keep my break down as mathematically independent and small as possible so I can spread it over different systems and then efficiently join them. –  Lostsoul Sep 25 '11 at 2:23
    
If the problem is as user3296 stated it, and I'm not mistaken, then it's guaranteed to take a long time for large numbers. If you have a sum of 1,000 with 30 variables, for examples, there could well be billions of billions of possible sums, so if you want to output every possible sum, your computer will necessarily perform billions of billions of calculations. –  Tanner Swett Sep 25 '11 at 3:52
    
@TannerL.Swett agreed. That was the problem I originally hit, but after following the above plan, I am able to scale over more than one cpu(my system currently has 4 cores). My problem is, depending on the specific variables I don't think I am getting the correct answer. –  Lostsoul Sep 25 '11 at 4:24
add comment

2 Answers 2

up vote 6 down vote accepted

Ah, here we go: this one's the problem of enumerating the number of ways to make change. This problem has been discussed before on this site and in a nice textbook, but let's specialize to your problem.

Consider a country, Lost-soulia, where the currency unit is the Lostie. The existing coins of the realm have the values of 1 Lostie, 2 Losties, and 4 Losties. You're asking how many ways can one have 10 Losties in the coins of the realm.

One way to solving this makes use of the concept of generating functions; specifically, consider the generating function

$$\frac1{(1-a x)(1-b x^2)(1-c x^4)}$$

where $a,b,c$ each correspond to the number of each denomination. To solve your problem of representing 10 Losties in coins, we expand the generating function as a Maclaurin series, and take the coefficient of $x^{10}$. For this case, the required coefficient is

$$a^{10}+a^8 b+a^6 b^2+a^6 c+a^4 b^3+a^4 b c+a^2 b^4+a^2 b^2 c+a^2 c^2+b^5+b^3 c+b c^2$$

We count twelve terms in this result, corresponding to your twelve ways of representing 10 Losties in terms of Lostie coins. Each term can be interpreted as a particular partition of 10; for instance, the term $a^4 bc$ corresponds to having 4 1-Lostie coins, 1 2-Lostie coin, and 1 4-Lostie coin, which totals to 10 Losties. (The exponents of the $a,b,c$ correspond to the counts of each coin.)

We can generalize. If for instance Lost-soulia decides to release a brand spanking new 3 Lostie coin, you just need to change your generating function to

$$\frac1{(1-a x)(1-b x^2)(1-c x^4)(1-d x^3)}$$

where $d$ corresponds to the count of 3-Lostie coins.The coefficient of $x^{10}$ in the series expansion is

$$\begin{split}a^{10}+a^8 b+a^7 d+a^6 b^2+a^6 c+a^5 b d+a^4 b^3+a^4 b c+a^4 d^2+a^3 b^2 d+a^3 c d+a^2 b^4+\\ a^2 b^2 c+a^2 b d^2+a^2 c^2+a b^3 d+a b c d+a d^3+b^5+b^3 c+b^2 d^2+b c^2+c d^2\end{split}$$

which has 23 terms, so you have 23 ways of having 10 Losties in coins. The $abcd$ term for instance corresponds to partitioning 10 as $1+2+4+3$, and $ab^3 d$ corresponds to partitioning 10 as $1+2+2+2+3$.


I gave a short Mathematica routine for the change-making problem in the comments, but that version has a bug (try MakeChange[8, {2, 7}]). Here is a more robust version of that routine:

MakeChange[n_Integer?Positive, v_?VectorQ] := Module[{l = Length[v], x}, 
   Exponent[#, Array[C, l]] & /@ 
    Flatten[{Expand[
        SeriesCoefficient[1/Apply[Times, 1 - Array[C, l] x^v], 
          {x, 0, n}]] /. Plus -> List}]] /;
VectorQ[v, (IntegerQ[#] && Positive[#]) &]

Much later: It turns out that the functionality of MakeChange[] is already done by the intrinsic functions IntegerPartitions[] and FrobeniusSolve[]. Still, I think the routine is a nice illustration of generating functions...

There are more efficient methods for solving the Frobenius problem, using methods from graph theory and integer programming; you can search the web for papers discussing these methods for generating and counting integer partitions.

share|improve this answer
    
You may have misread the question slightly. It asks not how to calculate how many ways there are to make change, but to calculate a list of the ways there are to make change. –  Tanner Swett Sep 25 '11 at 4:12
    
Er, that's why you unpack and interpret the terms of the coefficient of the series expansion, @Tanner. To use $a^{10}+a^8 b+a^6 b^2+a^6 c+a^4 b^3+a^4 b c+a^2 b^4+a^2 b^2 c+a^2 c^2+b^5+b^3 c+b c^2$ as an example again, this says that you can have 10 Losties as 10 1-Lostie coins ($a^{10}$), 8 1-Lostie and 1 2-Lostie coins ($a^8 b$), 6 1-Lostie and 2 2-Lostie coins ($a^6 b^2$)... hopefully you've gotten the hang of it at this point. –  J. M. Sep 25 '11 at 4:22
    
Anyway, here's a Mathematica implementation of the idea: MakeChange[n_Integer?Positive, v_?VectorQ] := Module[{l = Length[v], x}, Exponent[#, Array[C, l]] & /@ Apply[List, Expand[SeriesCoefficient[1/Apply[Times, 1 - Array[C, l] x^v], {x, 0, n}]]]] /; VectorQ[v, (IntegerQ[#] && Positive[#]) &]. Try MakeChange[10, {1, 2, 4}] for instance. –  J. M. Sep 25 '11 at 4:26
    
I'm new to math so it'll take a few hours to understand this but Tanner is correct, I may not understand this fully but I am actually not trying to create the whole list but figuring out how to compute a table for each value so I can rejoin them quickly on other machines. I will study this and may have mistunderstood though. –  Lostsoul Sep 25 '11 at 4:36
2  
Wow..amazing..You guys are so helpful. I code in python if that helps. When I started learning math I installed Mathematica but haven't used it, you're giving me a reason! I'll try to understand and try it. Thanks so much, JM. –  Lostsoul Sep 25 '11 at 4:46
show 6 more comments

I will use the statement of the problem as user3296 gave it: "Write a computer program which, given a positive integer $n$ and a list of positive integers $S = \{m_1, m_2, \ldots, m_k\}$ as input, produces a list of every way of writing the number $n$ as a sum of elements of $S$."

The trick to solving many problems of this type is to break each case down exactly into smaller cases. For this particular problem, we can break down each problem involving a universe into multiple problems involving the next smaller universe, and that one into multiple problems involving the next smaller universe, and so on, until the universe is empty. With an empty universe, there's only one number we can make: 0.

More formally, to solve this problem, we use recursion on $S$. Consider the first element of $S$, $m_1$, and assume that the problem has already been solved for $\{m_2, m_3, \ldots, m_k\}$. If $n \ge m_1$, then we can use it once. Whether or not $n \ge m_1$, we can ignore $m_1$ and move on to the next element of the universe.

In pseudocode, our recursive function looks like this:

findSums(n, S) (if S is not empty):
    Start with an empty list, L, of sums.
    Is n greater than or equal to m1?
        If so, add all elements of findSums(n - m1, S) to L,
        and then put "m1 +" in front of each element of L.
    Add all elements of findSums(n, S \ m1) to L.
    We are done.  Return L.

findSums(n, emptyset) (if n is not 0):
    Return the empty list.
    (There is no way to add elements of the empty set
    to get something positive.)

findSums(0, emptyset):
    Return the list containing only the empty sum.

In Haskell:

findSums n (s:ss) =
    (if n >= s then map (s:) (findSums (n-s) (s:ss)) else [])
    ++ sums n ss

findSums 0 [] = [[]]

findSums _ [] = []
share|improve this answer
    
Thanks Tanner. I'm doing this in python(and new to programming) so let me setup haskell and convert your code a bit to understand better..thank you Tanner! –  Lostsoul Sep 25 '11 at 4:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.