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
