Had to be a better way, though its performance isn’t crucial, of course. Thanks, Mike
Please reply to [email protected]. Sent from my iPad > On 18 Nov 2017, at 01:07, Raul Miller <[email protected]> wrote: > > blockmake=: (-@[ {."1&.> ] <@({.,"0 1 }.)"0 1~ 1+])i. > (5 blockmake 4) -: 4 makeblock 5 > 1 > > Thanks, > > -- > Raul > > > On Fri, Nov 17, 2017 at 1:14 PM, '[email protected]' via > Programming <[email protected]> wrote: >> Erling Helenas, Raul Miller, and others have come up with various >> methods to generate subsets of “restricted generating functions” (RGFs) >> suitable for the production of partitions of sets. Several of these >> have used Ruskey’s algorithm. >> >> I’ve found a fairly simple approach which has the benefits of (a) not >> being recursive, (b) being fairly easy to understand, and (c) not >> generating redundant data needing later filtering. It does, however, >> use a loop, albeit needing fewer loops than the final number of rows, >> ie RGFs . >> >> It saves a fair amount of space by using a character array of symbols >> rather than integers to represent the RGFs. A character string serves >> equally as well as an integer vector as left argument to </. for the >> generation of boxed partitions. >> >> Key features, which might be improved upon, include the local verb >> “ki” which yields the index of that element in an RGF which needs to be >> incremented in generating the next RGF, and a number of small look-up >> mini-arrays useful in finding the next appropriate few RGFs. >> >> Its performance compares favourably with other recent offerings. >> >> There is one main verb, “parMD”, and a helper verb, “makeblock”, >> which constructs one of the look-up arrays. >> >> Here it is; look out for line-wraps, though it looks ok this end! :- >> >> ========================================================================================== >> 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 >> ) >> >> >> ========================================================================================== >> >> eg - generate RGFs suitable for 4-partitions of 5 elements: >> parMD/ 4 5 >> 00123 >> 01023 >> 01123 >> 01203 >> 01213 >> 01223 >> 01230 >> 01231 >> 01232 >> 01233 >> >> (parMD/ 4 5)</."1 i.5 >> +---+---+---+---+ >> |0 1|2 |3 |4 | >> +---+---+---+---+ >> |0 2|1 |3 |4 | >> +---+---+---+---+ >> |0 |1 2|3 |4 | >> +---+---+---+---+ >> |0 3|1 |2 |4 | >> +---+---+---+---+ >> |0 |1 3|2 |4 | >> +---+---+---+---+ >> |0 |1 |2 3|4 | >> +---+---+---+---+ >> |0 4|1 |2 |3 | >> +---+---+---+---+ >> |0 |1 4|2 |3 | >> +---+---+---+---+ >> |0 |1 |2 4|3 | >> +---+---+---+---+ >> |0 |1 |2 |3 4| >> +---+---+---+---+ >> >> That's all for now! >> Mike >> >> ---------------------------------------------------------------------- >> 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
