Hi Mike, Thank you for the improvements. And thanks to Erling for comments and analysis.
Esa -----Original Message----- From: Programming [mailto:[email protected]] On Behalf Of 'Mike Day' via Programming Sent: Friday, October 27, 2017 2:26 PM To: [email protected] Subject: Re: [Jprogramming] Partitions Sorry, I haven’t got a useful direct response for Raul’s comment on this. BUT, here are a couple of amendments which seem to greatly improve on Lippu Esa’s par2. The main improvement hangs on the observation that rows in a such as 000102 and 000201 (spaces removed) are essentially the same. This identity can be exposed by means of i.~ , which returns 000305 for each of these examples. See “mdpart” Some further improvement arises from using a compound base, 1 2 3 ... instead of x in the #: expression, as exploited in “mdpart1” I’m copying from an iPad script (!!!), so apologies if it looks strange. I’m away from home, and emails from the laptop are inconvenient. This is the script: << NB. new file created mdpart =: 4 : 0 NB. after Lippu Esa's 'par2' NB. The key improvement is doing ~. on i.~"1 applied to a NB. Also, column 0 is all zero NB. tacit definition of array a: NB. a =. x ([ (] #~ (= #@~."1)) #~ ~.@:(i.~"1)@:(0,.#:) i.@^) <: y NB. More explicit form of definition of a: a =. ~. i.~"1 ] 0,. (ym1#x) #: i. x^ ym1 =. y - 1 a =. a#~ x = #@~."1 a NB. There's no need now to seek the nub of the boxed output: sort a </."1 i. y ) mdpart1 =: 4 : 0 NB. after 'mdpart' NB. use >: i. y instead of x as base for #: a =. ~. i.~"1 iy #: i. */ iy =. >: i.y a =. a#~ x = #@~."1 a NB. you can save memory for slightly more runtime by swapping the filters: NB. a =. iy #: i. */ iy =. >: i.y NB. a =. ~. i.~"1 a#~ x = #@~."1 a NB. There's no need now to seek the nub of the boxed output: sort a </."1 i. y ) >> end of script Snips from ‘terminal’ - sorry, I don’t know how to force fixed width! |:2 mdpart 5 +-------+-----+-----+-------+-------+-----+-------+-----+-----+-----+-------+-----+-----+-----+-----+ |0 |0 1 |0 1 2|0 1 2 3|0 1 2 4|0 1 3|0 1 3 4|0 1 4|0 2 |0 2 3|0 2 3 4|0 2 4|0 3 |0 3 4|0 4 | +-------+-----+-----+-------+-------+-----+-------+-----+-----+-----+-------+-----+-----+-----+-----+ |1 2 3 4|2 3 4|3 4 |4 |3 |2 4 |2 |2 3 |1 3 4|1 4 |1 |1 3 |1 2 4|1 2 |1 2 3| +-------+-----+-----+-------+-------+-----+-------+-----+-----+-----+-------+-----+-----+-----+-----+ ts 6!:2 , 7!:2@] (par2 -: mdpart) / 3 5 1 (par2 -: mdpart) / 3 5 1 (par2 -: mdpart) / 5 8 1 (mdpart -: mdpart1) / 5 8 1 ts'mdpart/ 5 8' 0.067471 3.67081e7 ts'mdpart1/ 5 8'. NB. faster here too! 0.035821 1.41636e7 ts'par2/ 5 8'. NB. Somewhat slower 12.1893 1.64228e8 Cheers, Mike Please reply to [email protected]. Sent from my iPad > On 26 Oct 2017, at 16:11, Mike Day <[email protected]> wrote: > > I was looking at par2 earlier today, with a view to making it tacit, and > noticed that removing duplicate solutions with ~. greatly increases the > running time. I suppose that’s because the array is boxed. Doing ~. after > the sort doesn’t help. > > Limited tests suggest the tacit version’s performance is similar to that for > the explicit one. > > Mike > > Please reply to [email protected]. > Sent from my iPad > >> On 26 Oct 2017, at 09:55, Erling Hellenäs <[email protected]> wrote: >> >> Hi all ! >> >> The last comment should be: >> >> NB. Select the unique combinations. Sort to display nicely >> sort ~. w >> >> Cheers, >> >> Erling >> >> >>> Den 2017-10-26 kl. 10:38, skrev Erling Hellenäs: >>> Hi all ! >>> >>> I analysed Esa Lippus solution. The printout is long, but here is the code >>> and my explanations. >>> >>> par2=: 4 : 0 >>> a=.(y#x) #: i. x^y >>> sort ~.((x=#@~."1 a)#a) </."1 i.y >>> ) >>> sort=: /:~ >>> 3 par2 5 >>> x=:3 >>> y=:5 >>> NB. All combinations of y elements >>> [a=:(y#x) #: i. x^y >>> NB. Select the combinations in which the y elements >>> NB. are distributed over x buckets >>> [v=: ((x=#@~."1 a)#a) >>> NB. Pack the elements in each bucket combination. >>> [w=:v </."1 i.y >>> NB. Sort to display nicely >>> sort ~. w >>> >>> Cheers, >>> >>> Erling Hellenäs >>> >>> >>>> Den 2017-10-26 kl. 07:07, skrev 'Skip Cave' via Programming: >>>> Lippu, >>>> >>>> Yes, your par2 is MUCH faster than Raul's nparts. If I have some time, I >>>> will put together a time/space test for all the proposed solutions. >>>> >>>> Skip >>>> >>>> Skip Cave >>>> Cave Consulting LLC >>>> >>>>> On Wed, Oct 25, 2017 at 1:58 PM, Lippu Esa <[email protected]> wrote: >>>>> >>>>> Hello, >>>>> >>>>> I get the following with the partition verb I posted last Thursday (J8.06 >>>>> and 4 core 2.9GHz CPU and 16GB RAM): >>>>> >>>>> par2=: 4 : 0 >>>>> a=.(y#x) #: i. x^y >>>>> sort ~.((x=#@~."1 a)#a) </."1 i.y >>>>> ) >>>>> >>>>> ts '#5 par2 8' >>>>> 4.15977615 151821824 >>>>> ts '# 6 par2 8' >>>>> 2.55073168 358252032 >>>>> >>>>> Esa >>>>> >>>>> -----Original Message----- >>>>> From: Programming [mailto:[email protected]] On >>>>> Behalf Of 'Skip Cave' via Programming >>>>> Sent: Wednesday, October 25, 2017 8:12 PM >>>>> To: [email protected] >>>>> Subject: Re: [Jprogramming] Partitions >>>>> >>>>> Raul got it right with his nparts verb. In my original example of par, I >>>>> constructed the required output of par by hand. In that process, I >>>>> overlooked the majority of the possible combinations of the ways that 5 >>>>> items could be separated into 3 containers. That caused confusion in the >>>>> various attempts to implement what I proposed. I wasn't very thorough in >>>>> vetting my example output, and Mike valiantly tried to point out the flaws >>>>> in my proposal. Raul showed how much I missed clearly in my par example >>>>> when he demonstrated: >>>>> >>>>> #3 nparts 5 >>>>> 25 >>>>> #3 par 5 >>>>> 6 >>>>> >>>>> Rob also pointed out the issue in his posts. Erling's v7 verb got to the >>>>> same result as Raul's nparts. >>>>> >>>>> The number of possible partitions of n objects grows rapidly with n: >>>>> >>>>> #3 nparts 5 >>>>> >>>>> 25 >>>>> >>>>> #3 nparts 6 >>>>> >>>>> 90 >>>>> >>>>> #3 nparts 7 >>>>> >>>>> 301 >>>>> >>>>> #3 nparts 8 >>>>> >>>>> 966 >>>>> >>>>> >>>>> >>>>> Increasing the number of partitions reduces the number of combinations but >>>>> significantly increases execution time with Raul's nparts : >>>>> >>>>> >>>>> #4 nparts 8 >>>>> >>>>> 1701 >>>>> >>>>> #5 nparts 8 >>>>> >>>>> 1050 >>>>> >>>>> #6 nparts 8 >>>>> >>>>> 266 >>>>> >>>>> >>>>> The 5 #nparts 8 took over 30 seconds to run on my i7 laptop. The #6 >>>>> nparts >>>>> 8 took about 3 minutes. >>>>> >>>>> >>>>> Is there a more computationally efficient way to calculate the partitions? >>>>> >>>>> >>>>> Skip >>>>> ---------------------------------------------------------------------- >>>>> For information about J forums see http://www.jsoftware.com/forums.htm >>>>> ---------------------------------------------------------------------- >>>>> For information about J forums see http://www.jsoftware.com/forums.htm >>>> ---------------------------------------------------------------------- >>>> For information about J forums see http://www.jsoftware.com/forums.htm >>> >>> ---------------------------------------------------------------------- >>> For information about J forums see http://www.jsoftware.com/forums.htm >> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
