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
