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...
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.
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.
Well, what I gave is the mathematical solution to your problem @Lostsoul. For a programmatic solution, there are efficient polynomial-time algorithms; I'll try to dig up references unless somebody beats me to it. If you have Mathematica on you, try the code I gave; if you have some other computing system, tell me and I'll see if I can translate to your favorite language.
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: You're very much welcome. I wrote that in version 8; if you're using an earlier version, quite a few modifications to MakeChange[] are needed.
Sorry, I am trying to run it but keep getting '$RecursionLimit::reclim: Recursion depth of 256 exceeded.' Your code is somewhat similar to python, I'll just work on converting it and running in that environment. I'll let you know the result.
when you say cells. is it suppose to look like a spreadsheet? I am using the notebook mode
i just tried rerunning with your Remove at the top..and got {{0, 0, 0}, {0, -[Infinity], 0}}
I sort of don't understand your description though..I know I can't break down recusions into different proceses.
I'm not sure if it'll be formated correctly but here's the code i have(python)
#sorts each element of seq and returns it def orderedInnerLists(seq): return map(sorted, seq)
#returns a copy of seq with duplicates removed def removeDuplicates(seq): ret = [] for value in seq: if value not in ret: ret.append(value) return ret
memoizedResults = {} def orderedPossibleSplits(value,validIncrements): memoizeKey = (value, tuple(validIncrements)) if memoizeKey in memoizedResults: return memoizedResults[memoizeKey] ret = [] for increment in validIncrements: if increment > value: continue
running print orderedPossibleSplits(10, [1,2,4]) gives the list..
so what I do is, take the universe 4,2,1 and run it pass the ordered splits function..
so first run is orderedPossibleSplits(2, [1]) then orderedPossibleSplits(4, [2])..then orderedPossibleSplits(10, [4])
I then have the master table, and run a lookup for 4 + 4 + 2..to break this down..
This way..I can not only split the generation process over different cpu's..I can spread the combination of the final result over different machines as well..
The problem is, there's a major flaw in my logic(like i said, if there's a 3 in there..or something similar)
Discussion between Lostsoul and J. M.
Discussion between Lostsoul and J. M.