I decided to investigate the inefficiency of the Skiena algorithm: timespacex 'Knuth 10' 0.000739266 11520 timespacex 'Skiena~ 10' 0.000520212 13568 timespacex 'Knuth 20' 0.011861 202112 timespacex 'Skiena~ 20' 0.00808606 294656 timespacex 'Knuth 30' 0.0345268 3.15174e6 timespacex 'Skiena~ 30' 0.0318853 4.40192e6 timespacex 'Knuth 40' 0.233694 2.51721e7 timespacex 'Skiena~ 40' 0.281741 3.51424e7 $Knuth 40 37338 40 $Knuth 30 5604 30
We start seeing the inefficiency for result sizes on the order of 10k rows. (I'm not refining that result because the inefficiency is too trivial to be significant at this stage.) timespacex 'Skiena~ 50' 2.08078 2.74745e8 timespacex 'Knuth 50' 1.3436 2.01333e8 timespacex 'Skiena~ 60' 12.6631 1.14088e9 timespacex 'Knuth 60' 6.25185 8.05313e8 $Knuth 50 204226 50 $Knuth 60 966467 60 The inefficiency becomes significant (factor of 2) for result sizes on the order of half a million rows. Of course in practice you'd probably want to compute this once and the use the stored result. -- Raul On Mon, Oct 13, 2014 at 11:26 PM, Devon McCormick <devon...@gmail.com> wrote: > http://www.jsoftware.com/jwiki/DevonMcCormick/HAP_AIP > is an essay by Howard Peele on "All Integer Partitions". > > On Mon, Oct 13, 2014 at 9:31 PM, Jon Hough <jgho...@outlook.com> wrote: > >> If you search jsoftware for >> Partitions r.e. boss >> >> There is a dictionary page about power u^:v >> >> At the bottom of the page is a verb for finding Partitions, by r.e. boss. >> It may be helpful. >> >> --- Original Message --- >> >> From: "Devon McCormick" <devon...@gmail.com> >> Sent: October 14, 2014 9:07 AM >> To: "J-programming forum" <programm...@jsoftware.com> >> Subject: Re: [Jprogramming] J code for integer partitions & scale-weight >> balancing? >> >> Have you spoken w/Howard Peele about the latter one? >> >> On Mon, Oct 13, 2014 at 6:19 PM, Murray Eisenberg < >> murrayeisenb...@gmail.com >> > wrote: >> >> > Has anybody translated into J the solutions to two problems posed in the >> > most recent Vector (Vol 26, Nos. 2 & 3) and solved there in APL, namely: >> > >> > (1) Determining the masses of a complex system of scales (levers) and >> > weights -- Brian Becker's article "One reason that APL is so cool". >> > >> > (2) Finding all partitions of a given integer n into exactly k distinct >> > positive integers -- Don Baronet's article, "A tool of thought". >> > >> > If so, would you be willing to share? >> > >> > I ask because I'm a bit rusty with J, and have no access to any modern >> APL >> > interpreter for OS X my Mac. >> > >> > --- >> > Murray Eisenberg murrayeisenb...@gmail.com >> > 503 King Farm Blvd #101 Home (240)-246-7240 >> > Rockville, MD 20850-6667 Mobile (413)-427-5334 >> > >> > >> > >> > >> > >> > ---------------------------------------------------------------------- >> > For information about J forums see http://www.jsoftware.com/forums.htm >> > >> >> >> >> -- >> Devon McCormick, CFA >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> > > > > -- > Devon McCormick, CFA > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
