(it's kind of silly, though, since in real life you'd just use i.) Thanks,
-- Raul On Mon, Nov 20, 2017 at 6:27 AM, Raul Miller <[email protected]> wrote: > Note also that the 256 parMD 256 case could have been addressed by > using |. instead of }. when defining a > > Thanks, > > -- > Raul > > > On Mon, Nov 20, 2017 at 6:20 AM, 'Mike Day' via Programming > <[email protected]> wrote: >> Yes, the char array uses less space. Also, as has been observed before, >> the main work is deriving the “RGFs” and there’s a considerable overhead >> in turning them into their partition equivalents. Try removing the key >> operation. >> >> Mike >> >> Please reply to [email protected]. >> Sent from my iPad >> >>> On 20 Nov 2017, at 10:33, Erling Hellenäs <[email protected]> wrote: >>> >>> Hi all! >>> >>> I made a comparison. >>> >>> They are very similar in theirtime requirements, but Mike Days version uses >>> considerably less space. >>> >>> This might be mainly due to the choice of ascii representation of theresult. >>> >>> Some consequences of this choice: >>> >>> x=:15 >>> y=:15 >>> x parMD y >>> 0123456789:;<=> >>> x SetPartitionsGenerateF y >>> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 >>> >>> x=:255 >>> y=:256 >>> ts'x parMD y' >>> |index error: parMD >>> | list=.a {~list >>> ts'x SetPartitionsGenerateF y' >>> 2.53384 1.73658e8 >>> >>> See below. >>> >>> Cheers, >>> >>> Erling Hellenäs >>> >>> ----Output--- >>> >>> x=:1 >>> y=:1 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> 1 >>> >>> x=:1 >>> y=:2 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> 1 >>> >>> x=:1 >>> y=:3 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> 1 >>> >>> x=:2 >>> y=:4 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> 1 >>> >>> x=:2 >>> y=:5 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> 1 >>> >>> x=:3 >>> y=:5 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> 1 >>> >>> >>> x=:5 >>> y=:10 >>> >>> ts'x SetPartitionsGenerateF y' >>> 0.0217097 8.39974e6 >>> ts'x parMD y' >>> 0.0381484 796032 >>> >>> x=:6 >>> y=:12 >>> >>> ts'x SetPartitionsGenerateF y' >>> 1.03637 2.68448e8 >>> ts'x parMD y' >>> 1.06117 2.51788e7 >>> >>> ---- 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 >>> v5=. /:~ v4 >>> (/: #&.> v5){ v5 >>> ) >>> >>> compare=: -:&:normalize >>> >>> NB. Mike Day >>> >>> NB. produce a table of "restricted growth functions" (rgf) (strings of >>> symbols) subject to >>> NB. requirement that each "function" (or string) includes at least one >>> instance of each symbol >>> NB. eg 001100 is an rgf, but if all the symbols '012' are required, it's >>> not suitable here >>> NB. eg an rgf such as 001213 is a suitable equivalent to >>> NB. |01|24|3|5|, a 4-partition for 6 elements >>> >>> NB. Any symbols may be used, but they are subject to an implicit or >>> explicit ordering. >>> >>> parMD =: 3 : 0 >>> y parMD~ <:#y >>> : >>> k =. <: x >>> NB. starting/current row >>> if. 1 = #y do. >>> list =. ,: cur =. (-y){.i.x >>> else. NB. Admit a starting row (of integers, not symbols) other than 0 0 >>> 0 1 2 ... >>> NB. NB. not tested here for validity!!! >>> list =. ,: cur =. y >>> end. >>> n =. #cur >>> a =. a. }.~ a. i. '0' NB. symbol list - arbitrary, but '012...' here >>> if. x > n do. NB. special-case impossible partitions >>> ' '$~ 0, n >>> elseif. x = 1 do. NB. special-case 1-partition >>> ,: n#{.a >>> elseif. x = 2 do. NB. special-case 2-partition >>> a{~ (n#2) #: }. i. 2 ^ n-1 >>> elseif. x = n do. NB. special-case n-partition >>> ,: n{.a >>> elseif. 1 do. >>> NB. I use the term k-partition, below, loosely - it should be x-partition >>> or (k+1)-partn. >>> list =. a {~ list NB. output as char array, offset so that 0 1 2 ... >>> <==> '012...' >>> NB. end =. k <. i. n NB. preset last row if required for stopping >>> condition >>> incr =. =/~ i.n NB. look-up array for incrementing i{cur >>> blnk =. +/\ incr NB. look-up array for blanking all elements after >>> i{cur >>> block=. x makeblock n NB. look-up array for forcing "new" rows to be >>> k-partition equivalents. >>> ki =. >:@i:&1@:(}. < k <. >:@:(>./\)@:}:) NB. restricted growth >>> function index finder, >>> NB. modified for limitation >>> to 1+k symbols >>> while. n | i =. ki cur do. NB. test new index - stop if = n >>> NB. one of several possible stopping conditions - >>> could test cur -: end >>> new =. (i{incr) + cur*i{blnk NB. next suitable "restricted growth >>> function" >>> mx =. >./ new NB. ALL values 0 1 2 ... k MUST appear for a >>> k-partition >>> NB. Adjust "new" if not already a k-partition equivalent, and expand to >>> several rows >>> new =. new +"1 >mx { block >>> NB. eg 00101000 (invalid k-part if x>2) becomes 00101023, 00101123 if (and >>> only if) x = 4 >>> list =. list, new { a >>> cur =. {: new >>> end. >>> list >>> end. >>> ) >>> >>> NB. assemble look-up array of blocks >>> NB. eg >>> NB. 4 makeblock 5 >>> NB. +---------+---------+---------+---------+ >>> NB. |0 0 1 2 3|0 0 0 2 3|0 0 0 0 3|0 0 0 0 0| >>> NB. | |0 0 1 2 3|0 0 0 1 3|0 0 0 0 1| >>> NB. | | |0 0 0 2 3|0 0 0 0 2| >>> NB. | | | |0 0 0 0 3| >>> NB. +---------+---------+---------+---------+ >>> makeblock =: 3 : 0 >>> makeblock/ y >>> : >>> NB. a work-a-day method, not a smart implementation! >>> m =. 0 >>> b =. '' >>> i =. i. x >>> while. x >: m =. >: m do. >>> b =. b, < (i.m),. m#,: i =. }. i >>> end. >>> (-y){."1 each b >>> ) >>> >>> >>> NB. Erling Hellenäs >>> >>> SetPartitionsGenerateF =: 4 : 0 >>> NB. Generate all set partitions with k subsets from >>> NB. an original set with n unique items. >>> NB. x - number of subsets >>> NB. y - number of items in the set to partition >>> NB. Result - table of integers >>> NB. -each row is a generated set partition >>> NB. -columns contain the subset number of the items >>> NB. with the corresponding position in the set to >>> NB. partition. >>> NB. Algorithm from Frank Ruskey: Combinatorial Generation >>> NB. Working Version (1j-CSC 425/520). >>> (,: i.y) SPGF (x-1);y-1 >>> ) >>> >>> SPGF =: 4 : 0 >>> 'k n' =. y >>> r=. (0,_1{.$x)$0 >>> if. k=n do. >>> r=.x >>> else. >>> s=.n {."1 x >>> e=.(n+1)}."1 x >>> a=.,/s ( [,"1 1 (i.k+1),"0 1 ])"1 e >>> r=.r, a SPGF k;n-1 >>> if. k > 0 do. >>> a=.s,.k,.e >>> r=.r, a SPGF (k-1);n-1 >>> end. >>> end. >>> r >>> ) >>> >>> x=:1 >>> y=:1 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> >>> x=:1 >>> y=:2 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> >>> x=:1 >>> y=:3 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> >>> x=:2 >>> y=:4 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> >>> x=:2 >>> y=:5 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> >>> x=:3 >>> y=:5 >>> >>> EH=:(x SetPartitionsGenerateF y)</."1 i.y >>> MD=:(x parMD y) </."1 i.y >>> EH compare MD >>> >>> >>> x=:5 >>> y=:10 >>> >>> ts'x SetPartitionsGenerateF y' >>> ts'x parMD y' >>> >>> x=:6 >>> y=:12 >>> >>> ts'x SetPartitionsGenerateF y' >>> ts'x parMD y' >>> >>> >>>> Den 2017-11-17 kl. 19:14, skrev '[email protected]' via >>>> Programming: >>>> NB. produce a table of "restricted growth functions" (rgf) (strings of >>>> symbols) subject to >>>> NB. requirement that each "function" (or string) includes at least one >>>> instance of each symbol >>>> NB. eg 001100 is an rgf, but if all the symbols '012' are required, >>>> it's not suitable here >>>> NB. eg an rgf such as 001213 is a suitable equivalent to >>>> NB. |01|24|3|5|, a 4-partition for 6 elements >>>> >>>> NB. Any symbols may be used, but they are subject to an implicit or >>>> explicit ordering. >>>> >>>> parMD =: 3 : 0 >>>> y parMD~ <:#y >>>> : >>>> k =. <: x >>>> NB. starting/current row >>>> if. 1 = #y do. >>>> list =. ,: cur =. (-y){.i.x >>>> else. NB. Admit a starting row (of integers, not symbols) other than >>>> 0 0 0 1 2 ... >>>> NB. NB. not tested here for validity!!! >>>> list =. ,: cur =. y >>>> end. >>>> n =. #cur >>>> a =. a. }.~ a. i. '0' NB. symbol list - arbitrary, but '012...' >>>> here >>>> if. x > n do. NB. special-case impossible partitions >>>> ' '$~ 0, n >>>> elseif. x = 1 do. NB. special-case 1-partition >>>> ,: n#{.a >>>> elseif. x = 2 do. NB. special-case 2-partition >>>> a{~ (n#2) #: }. i. 2 ^ n-1 >>>> elseif. x = n do. NB. special-case n-partition >>>> ,: n{.a >>>> elseif. 1 do. >>>> NB. I use the term k-partition, below, loosely - it should be x- >>>> partition or (k+1)-partn. >>>> list =. a {~ list NB. output as char array, offset so that 0 1 2 >>>> ... <==> '012...' >>>> NB. end =. k <. i. n NB. preset last row if required for stopping >>>> condition >>>> incr =. =/~ i.n NB. look-up array for incrementing i{cur >>>> blnk =. +/\ incr NB. look-up array for blanking all elements >>>> after i{cur >>>> block=. x makeblock n NB. look-up array for forcing "new" rows to be k- >>>> partition equivalents. >>>> ki =. >:@i:&1@:(}. < k <. >:@:(>./\)@:}:) NB. restricted growth >>>> function index finder, >>>> NB. modified for >>>> limitation to 1+k symbols >>>> while. n | i =. ki cur do. NB. test new index - stop if = n >>>> NB. one of several possible stopping conditions - >>>> could test cur -: end >>>> new =. (i{incr) + cur*i{blnk NB. next suitable "restricted growth >>>> function" >>>> mx =. >./ new NB. ALL values 0 1 2 ... k MUST appear for a k- >>>> partition >>>> NB. Adjust "new" if not already a k-partition equivalent, and expand >>>> to several rows >>>> new =. new +"1 >mx { block >>>> NB. eg 00101000 (invalid k-part if x>2) becomes 00101023, 00101123 if >>>> (and only if) x = 4 >>>> list =. list, new { a >>>> cur =. {: new >>>> end. >>>> list >>>> end. >>>> ) >>>> >>>> NB. assemble look-up array of blocks >>>> NB. eg >>>> NB. 4 makeblock 5 >>>> NB. +---------+---------+---------+---------+ >>>> NB. |0 0 1 2 3|0 0 0 2 3|0 0 0 0 3|0 0 0 0 0| >>>> NB. | |0 0 1 2 3|0 0 0 1 3|0 0 0 0 1| >>>> NB. | | |0 0 0 2 3|0 0 0 0 2| >>>> NB. | | | |0 0 0 0 3| >>>> NB. +---------+---------+---------+---------+ >>>> makeblock =: 3 : 0 >>>> makeblock/ y >>>> : >>>> NB. a work-a-day method, not a smart implementation! >>>> m =. 0 >>>> b =. '' >>>> i =. i. x >>>> while. x >: m =. >: m do. >>>> b =. b, < (i.m),. m#,: i =. }. i >>>> end. >>>> (-y){."1 each b >>>> ) >>> >>> ---------------------------------------------------------------------- >>> 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
