I got interested in trying to optimize this problem even further. Here are the results:
https://gist.github.com/jwmerrill/5b364d1887f40f889142 I was able to get the benchmark down to a few microseconds (or ~100 microseconds if you count the time to build a look up table). Either way, it's a pretty good improvement over 1+ seconds :-) The main trick is to represent a set of digits 1-9 as a binary integer. There are only 2^9=512 such sets, so you can pack any of them into an Int16. Then you can precompute the sum of each set and store those in a look up table, so that finding the ways to decompose a given number is just a table lookup. I think this is a pretty nice example of how Julia's dispatch system let you have complex views and operations over a very simple data structure (in this case, a single integer), with essentially 0 overhead. On Monday, October 19, 2015 at 7:39:03 AM UTC-4, Patrick Useldinger wrote: > > Hello > true but no summand may appear twice, and only numbers 1 to 9 may be used. > For example, (10, 3) yields > > Array[Int16[2,3,5],Int16[1,4,5],Int16[1,3,6],Int16[1,2,7]] > > Regards, > -Patrick >
