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
