Oops, I meant "That said, parRuskey still is more efficient for the case where x = y-1 and and y>3 ..."
(It's slower for the case where x=y-2 ...) Sorry about that, -- Raul On Mon, Oct 30, 2017 at 10:43 AM, Raul Miller <[email protected]> wrote: > Hmm... you're right, that deals with some cases quite a bit better than mine. > > I can dip into most of them like this: > > parRDM=:4 :0 > select. x > case.1 do. > ,.< i.y > case.2 do. > ((y#2)#:"1 0 }.i.2^y-1) </."1 i.y > case.y do. > ,:<"0 i.y > case.do. > x (1+y-x) P y > end. > ) > > ... keeping the definition of P (and combine) from > http://jsoftware.com/pipermail/programming/2017-October/049423.html > > That said, parRuskey still is more efficient for the case where x = > y-2 and and y>3 and that's worth some thought. > > Generally speaking, parRuskey has an advantage of working with > partition id rather than partition contents, until the very last step. > That's a clean performance advantage (no boxed arrays for most of the > work). But ... still needs thought. > > Thanks, > > -- > Raul > > > > On Mon, Oct 30, 2017 at 7:01 AM, Erling Hellenäs > <[email protected]> wrote: >> Hi all! >> >> Here is the Ruskey algorithm, right from the book. >> >> It's a good one, even in J which is not made for this kind of code. >> >> Maybe it can be improved? >> >> -----Project---- >> >> ts=: 6!:2 , 7!:2@] NB. Time and space >> >> S =: 4 : 0 >> >> if. x=y do. >> >> r=:r,a >> >> else. >> >> for_i. i.x do. >> >> a=: i (y-1) } a >> >> x S y-1 >> >> a=: (y-1) (y-1) } a >> >> end. >> >> if. x > 1 do. >> >> a=: (x-1) (y-1) } a >> >> (x-1) S y-1 >> >> a=: (y-1) (y-1) } a >> >> end. >> >> end. >> >> ) >> >> >> >> parRuskey =: 4 : 0 >> >> a=: i. y >> >> r=: (0,y)$0 >> >> x S y >> >> r </."1 i.y >> >> ) >> >> >> 2 parRuskey 3 >> >> 3 parRuskey 5 >> >> >> ts'5 parRuskey 10' >> >> >> -----Printout------ >> >> >> 2 parRuskey 3 >> ┌───┬───┐ >> │0 2│1 │ >> ├───┼───┤ >> │0 │1 2│ >> ├───┼───┤ >> │0 1│2 │ >> └───┴───┘ >> 3 parRuskey 5 >> ┌─────┬─────┬─────┐ >> │0 3 4│1 │2 │ >> ├─────┼─────┼─────┤ >> │0 4 │1 3 │2 │ >> ├─────┼─────┼─────┤ >> │0 4 │1 │2 3 │ >> ├─────┼─────┼─────┤ >> │0 2 4│1 │3 │ >> ├─────┼─────┼─────┤ >> │0 4 │1 2 │3 │ >> ├─────┼─────┼─────┤ >> │0 1 4│2 │3 │ >> ├─────┼─────┼─────┤ >> │0 3 │1 4 │2 │ >> ├─────┼─────┼─────┤ >> │0 │1 3 4│2 │ >> ├─────┼─────┼─────┤ >> │0 │1 4 │2 3 │ >> ├─────┼─────┼─────┤ >> │0 2 │1 4 │3 │ >> ├─────┼─────┼─────┤ >> │0 │1 2 4│3 │ >> ├─────┼─────┼─────┤ >> │0 1 │2 4 │3 │ >> ├─────┼─────┼─────┤ >> │0 3 │1 │2 4 │ >> ├─────┼─────┼─────┤ >> │0 │1 3 │2 4 │ >> ├─────┼─────┼─────┤ >> │0 │1 │2 3 4│ >> ├─────┼─────┼─────┤ >> │0 2 │1 │3 4 │ >> ├─────┼─────┼─────┤ >> │0 │1 2 │3 4 │ >> ├─────┼─────┼─────┤ >> │0 1 │2 │3 4 │ >> ├─────┼─────┼─────┤ >> │0 2 3│1 │4 │ >> ├─────┼─────┼─────┤ >> │0 3 │1 2 │4 │ >> ├─────┼─────┼─────┤ >> │0 1 3│2 │4 │ >> ├─────┼─────┼─────┤ >> │0 2 │1 3 │4 │ >> ├─────┼─────┼─────┤ >> │0 │1 2 3│4 │ >> ├─────┼─────┼─────┤ >> │0 1 │2 3 │4 │ >> ├─────┼─────┼─────┤ >> │0 1 2│3 │4 │ >> └─────┴─────┴─────┘ >> >> ts'5 parRuskey 10' >> 0.209091 3.89519e7 >> >> >> Cheers, >> >> >> Erling Hellenäs >> >> >> >> Den 2017-10-29 kl. 01:29, skrev Erling Hellenäs: >>> >>> Algorithm 4.23 here maybe: >>> http://www.1stworks.com/ref/ruskeycombgen.pdf >>> /Erling >>> >>> On 2017-10-28 23:46, Erling Hellenäs wrote: >>>> >>>> Hi all! >>>> >>>> Here is a reference to Knuth, and descriptions of how to enumerate these >>>> set partitions: >>>> https://math.stackexchange.com/questions/222780/enumeration-of-partitions >>>> >>>> There are solutions: >>>> >>>> http://www.informatik.uni-ulm.de/ni/Lehre/WS03/DMM/Software/partitions.pdf >>>> https://blogs.msdn.microsoft.com/oldnewthing/20140324-00/?p=1413 >>>> >>>> https://codereview.stackexchange.com/questions/1526/finding-all-k-subset-partitions/1944#1944 >>>> >>>> Cheers, >>>> >>>> Erling Hellenäs >>>> >>>> >>>> >>>> >>>> >>>> >>>> On 2017-10-28 19:06, Erling Hellenäs wrote: >>>>> >>>>> Hi all ! >>>>> >>>>> I tried to analyse Mikes version. >>>>> >>>>> --- Project --- >>>>> >>>>> parMD=: 4 : 0 >>>>> >>>>> a =. ~. i.~"1 iy #: i. */ iy =. >: i.y >>>>> >>>>> a =. a#~ x = #@~."1 a >>>>> >>>>> sort a </."1 i. y >>>>> >>>>> ) >>>>> >>>>> sort=: /:~ >>>>> >>>>> 2 parMD 4 >>>>> >>>>> x=:2 >>>>> >>>>> y=:4 >>>>> >>>>> NB. >>>>> >>>>> [iy =: >: i.y >>>>> >>>>> [v=: i. */ iy >>>>> >>>>> NB. You put item 0 in class 0. Now you can put item 1 there also >>>>> >>>>> NB. or you start a new class 1. You can put item y in class 0 to y. >>>>> >>>>> NB. This is the formula for that. Generating !y items. >>>>> >>>>> [w=: iy #: v >>>>> >>>>> NB. Normalize the class names so that a class starting in column n >>>>> always have name n >>>>> >>>>> NB. Example: Combinations with three items in class 0 and the forth in >>>>> class 1, 2 or 3 are equal. >>>>> >>>>> NB. The second class gets the name 3 since it starts in column 3 >>>>> >>>>> [o=:i.~"1 w >>>>> >>>>> NB. Remove class combinations which are equal. >>>>> >>>>> [a=: ~. o >>>>> >>>>> NB. Select the class combinations with x different classes. >>>>> >>>>> [a =. a#~ x = #@~."1 a >>>>> >>>>> NB. Pack the items in the boxes >>>>> >>>>> [p=:a </."1 i. y >>>>> >>>>> NB.Sort to display nicely. >>>>> >>>>> [sort p >>>>> >>>>> >>>>> ---Output--- >>>>> >>>>> >>>>> 2 parMD 4 >>>>> ┌─────┬─────┐ >>>>> │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 │ >>>>> └─────┴─────┘ >>>>> x=:2 >>>>> y=:4 >>>>> NB. >>>>> [iy =: >: i.y >>>>> 1 2 3 4 >>>>> [v=: i. */ iy >>>>> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 >>>>> NB. You put item 0 in class 0. Now you can put item 1 there also >>>>> NB. or you start a new class 1. You can put item y in class 0 to y. >>>>> NB. This is the formula for that. Generating !y items. >>>>> [w=: iy #: v >>>>> 0 0 0 0 >>>>> 0 0 0 1 >>>>> 0 0 0 2 >>>>> 0 0 0 3 >>>>> 0 0 1 0 >>>>> 0 0 1 1 >>>>> 0 0 1 2 >>>>> 0 0 1 3 >>>>> 0 0 2 0 >>>>> 0 0 2 1 >>>>> 0 0 2 2 >>>>> 0 0 2 3 >>>>> 0 1 0 0 >>>>> 0 1 0 1 >>>>> 0 1 0 2 >>>>> 0 1 0 3 >>>>> 0 1 1 0 >>>>> 0 1 1 1 >>>>> 0 1 1 2 >>>>> 0 1 1 3 >>>>> 0 1 2 0 >>>>> 0 1 2 1 >>>>> 0 1 2 2 >>>>> 0 1 2 3 >>>>> NB. Normalize the class names so that a class starting in column n >>>>> always have name n >>>>> NB. Example: Combinations with three items in class 0 and the forth >>>>> in class 1, 2 or 3 are equal. >>>>> NB. The second class gets the name 3 since it starts in >>>>> column 3 >>>>> [o=:i.~"1 w >>>>> 0 0 0 0 >>>>> 0 0 0 3 >>>>> 0 0 0 3 >>>>> 0 0 0 3 >>>>> 0 0 2 0 >>>>> 0 0 2 2 >>>>> 0 0 2 3 >>>>> 0 0 2 3 >>>>> 0 0 2 0 >>>>> 0 0 2 3 >>>>> 0 0 2 2 >>>>> 0 0 2 3 >>>>> 0 1 0 0 >>>>> 0 1 0 1 >>>>> 0 1 0 3 >>>>> 0 1 0 3 >>>>> 0 1 1 0 >>>>> 0 1 1 1 >>>>> 0 1 1 3 >>>>> 0 1 1 3 >>>>> 0 1 2 0 >>>>> 0 1 2 1 >>>>> 0 1 2 2 >>>>> 0 1 2 3 >>>>> NB. Remove class combinations which are equal. >>>>> [a=: ~. o >>>>> 0 0 0 0 >>>>> 0 0 0 3 >>>>> 0 0 2 0 >>>>> 0 0 2 2 >>>>> 0 0 2 3 >>>>> 0 1 0 0 >>>>> 0 1 0 1 >>>>> 0 1 0 3 >>>>> 0 1 1 0 >>>>> 0 1 1 1 >>>>> 0 1 1 3 >>>>> 0 1 2 0 >>>>> 0 1 2 1 >>>>> 0 1 2 2 >>>>> 0 1 2 3 >>>>> NB. Select the class combinations with x different classes. >>>>> [a =. a#~ x = #@~."1 a >>>>> 0 0 0 3 >>>>> 0 0 2 0 >>>>> 0 0 2 2 >>>>> 0 1 0 0 >>>>> 0 1 0 1 >>>>> 0 1 1 0 >>>>> 0 1 1 1 >>>>> NB. Pack the items in the boxes >>>>> [p=:a </."1 i. 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│ >>>>> └─────┴─────┘ >>>>> NB.Sort to display nicely. >>>>> [sort p >>>>> ┌─────┬─────┐ >>>>> │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 │ >>>>> └─────┴─────┘ >>>>> >>>>> Cheers, >>>>> >>>>> Erling Hellenäs >>>>> >>>>> >>>>> >>>>> On 2017-10-28 17:08, 'Mike Day' via Programming wrote: >>>>>> >>>>>> 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 >>>>> >>>>> >>>>> >>>>> ---------------------------------------------------------------------- >>>>> 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
