Thanks for the update, Erling. I’m looking for a constructive approach, which is perhaps what Raul has been exploring. It probably won’t improve matters, if ever I get my head round it. I won’t have access to email for another 24 hours or so, so don’t hold your breath! Meanwhile, I’m pleased with the speed-up that you’ve confirmed for my modifications for some problem sizes.
Cheers, Mike Please reply to [email protected]. Sent from my iPad > On 28 Oct 2017, at 13:39, Erling Hellenäs <[email protected]> wrote: > > Hi all ! > > Current state with Mike Days modification of Esa Lippus algorithm.I managed > to improve my version. > > --- Project ... > ts=: 6!:2 , 7!:2@] NB. Time and space > > normalize=: 3 :0 > NB. The idea here is to normalize the representation so that > NB. the copies are adjacent. > NB. Sort buckets within each combination after first item in each bucket > v31=.(] /: {.&.>)"1 y > NB. Sort buckets within each combination after number of items in each bucket > v4=.(] /: #&.>)"1 v31 > NB. Sort > /:~ v4 > ) > > compare=: -:&:normalize > > NB. Esa Lippu > parEL=: 4 : 0 > a=.(y#x) #: i. x^y > sort ~.((x=#@~."1 a)#a) </."1 i.y > ) > > NB. Raul > parR=: (#~ 1 - a: e."1 ])@~.@([: /:~"1 i.@] </."1~ [ #.^:_1 [ i.@^ ]) > > > NB. Erling > NB. All combinations of y item > combE2=: 3 : 'm{.#:i.m=.(0~:#y)*<.2^y' > NB. Cartesian product > cpE=: 4 : ',/x ,"2 "2 _ y' > parE =: 4 : 0 > NB. All combinations of all items > v=.}.combE2 y > NB. Select combinations with less than or equal to 1+y-x items > v1=.((+/"1 v)<:1+y-x)#v > NB. All combinations in all buckets > v11=.((#v1),1,y)$,v1 > v21=.>cp&.>/x#<v11 > NB. Select combinations with one and only one of each number > v3=.(1=*/"1 +/"2 v21) # v21 > NB. The idea here is to normalize the representation so that > NB. the copies are adjacent. > NB. Sort buckets within each combination > v31=./:~"2 v3 > NB. Remove duplicates > v4=. ~.v31 > NB. Pack > v4 <@# i.y > ) > > NB. Mike Day modification of Esa Lippu algorithm > > parMD =: 4 : 0 > a =. ~. i.~"1 iy #: i. */ iy =. >: i.y > a =. a#~ x = #@~."1 a > sort a </."1 i. y > ) > > ---Printout--- > > > x=:1 > y=:1 > > [EL=:x parEL y > ┌─┐ > │0│ > └─┘ > [R=:x parR y > ┌─┐ > │0│ > └─┘ > [E=:x parE y > ┌─┐ > │0│ > └─┘ > [MD=:x parMD y > ┌─┐ > │0│ > └─┘ > EL compare R > 1 > EL compare E > 1 > EL compare MD > 1 > > x=:1 > y=:2 > > [EL=:x parEL y > ┌───┐ > │0 1│ > └───┘ > NB.[R=:x parR y - Length Error > [E=:x parE y > ┌───┐ > │0 1│ > └───┘ > [MD=:x parMD y > ┌───┐ > │0 1│ > └───┘ > EL compare R > 0 > EL compare E > 1 > EL compare MD > 1 > > x=:1 > y=:3 > > [EL=:x parEL y > ┌─────┐ > │0 1 2│ > └─────┘ > NB. R=:x parR y - Length Error > [E=:x parE y > ┌─────┐ > │0 1 2│ > └─────┘ > [MD=:x parMD y > ┌─────┐ > │0 1 2│ > └─────┘ > EL compare R > 0 > EL compare E > 1 > EL compare MD > 1 > > x=:2 > y=:4 > > [EL=:x parEL y > ┌─────┬─────┐ > │0 │1 2 3│ > ├─────┼─────┤ > │0 1 │2 3 │ > ├─────┼─────┤ > │0 1 2│3 │ > ├─────┼─────┤ > │0 1 3│2 │ > ├─────┼─────┤ > │0 2 │1 3 │ > ├─────┼─────┤ > │0 2 3│1 │ > ├─────┼─────┤ > │0 3 │1 2 │ > └─────┴─────┘ > [R=:x parR y > ┌─────┬─────┐ > │0 1 2│3 │ > ├─────┼─────┤ > │0 1 3│2 │ > ├─────┼─────┤ > │0 1 │2 3 │ > ├─────┼─────┤ > │0 2 3│1 │ > ├─────┼─────┤ > │0 2 │1 3 │ > ├─────┼─────┤ > │0 3 │1 2 │ > ├─────┼─────┤ > │0 │1 2 3│ > └─────┴─────┘ > [E=:x parE y > ┌─────┬─────┐ > │3 │0 1 2│ > ├─────┼─────┤ > │2 │0 1 3│ > ├─────┼─────┤ > │2 3 │0 1 │ > ├─────┼─────┤ > │1 │0 2 3│ > ├─────┼─────┤ > │1 3 │0 2 │ > ├─────┼─────┤ > │1 2 │0 3 │ > ├─────┼─────┤ > │1 2 3│0 │ > └─────┴─────┘ > [MD=:x parMD y > ┌─────┬─────┐ > │0 │1 2 3│ > ├─────┼─────┤ > │0 1 │2 3 │ > ├─────┼─────┤ > │0 1 2│3 │ > ├─────┼─────┤ > │0 1 3│2 │ > ├─────┼─────┤ > │0 2 │1 3 │ > ├─────┼─────┤ > │0 2 3│1 │ > ├─────┼─────┤ > │0 3 │1 2 │ > └─────┴─────┘ > EL compare R > 1 > EL compare E > 1 > EL compare MD > 1 > > x=:2 > y=:5 > > EL=:x parEL y > R=:x parR y > E=:x parE y > MD=:x parMD y > EL compare R > 1 > EL compare E > 1 > EL compare MD > 1 > > x=:3 > y=:5 > > EL=:x parEL y > R=:x parR y > E=:x parE y > MD=:x parMD y > EL compare R > 1 > EL compare E > 1 > EL compare MD > 1 > > x=:3 > y=:6 > > EL=:x parEL y > R=:x parR y > E=:x parE y > MD=:x parMD y > EL compare R > 1 > EL compare E > 1 > EL compare MD > 1 > > ts'x parEL y' > 0.00251336 403840 > ts'x parR y' > 0.00441964 465280 > ts'x parE y' > 0.0162486 2.33524e7 > ts'x parMD y' > 0.000315755 224640 > > Cheers, > > Erling > >> On 2017-10-28 06:35, Lippu Esa wrote: >> 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 > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
