Oops again, I meant a=:u:48+i.n I really need to build better posting habits when writing on a phone.
Thanks, -- Raul On Wednesday, November 22, 2017, Raul Miller <[email protected]> wrote: > Oops, sorry, yes. > > I was expecting exponential growth to make the results unrepresentable. > But that only happens at the low end (of the x values). > > I guess maybe just set a=:u:i.48+n > > That said, note that when x=y-1 you can use a result of the form > (1+=i.x)#"1 i.x > > Thanks, > > -- > Raul > > On Wednesday, November 22, 2017, 'Mike Day' via Programming < > [email protected] > <javascript:_e(%7B%7D,'cvml','[email protected]');>> wrote: > >> How’s that, Raul? >> >> Wouldn’t ParXXX / 300 400 (Heaven forbid!) need 300 things, whether >> integers, symbols or what you will? >> >> What have I misunderstood? >> >> Cheers, >> >> Mike >> >> >> Please reply to [email protected]. >> Sent from my iPad >> >> > On 22 Nov 2017, at 21:56, Raul Miller <[email protected]> wrote: >> > >> > The only case where you need more than 256 symbols is when the left >> > arg matches the right arg. >> > >> > For that case, it's reasonable to produce the result u:i.1,y >> > >> > Thanks, >> > >> > -- >> > Raul >> > >> > On Wed, Nov 22, 2017 at 2:05 PM, 'Mike Day' via Programming >> > <[email protected]> wrote: >> >> Here's another shot at a non-recursive constructive approach to >> generating >> >> RGFs. >> >> It continues to use characters to store and represent the RGFs. It >> would >> >> need >> >> reworking if there were more than 256 digits/symbols, though I think >> we'd >> >> hit other >> >> problems before needing to worry about representation in such cases. >> >> >> >> Performance is reasonable if not outstanding, similar to or a bit >> better >> >> than parMD. >> >> >> >> I think it's a bit easier to understand than my earlier effort. I >> hope the >> >> comments in >> >> the following script help. >> >> >> >> NB. Please take care with line-wrapping... >> >> >> >> makeinsert =: 3 : 0 M. NB. to memoise or not to memoise? >> >> a =. a. |.~ a. i. '0' NB. symbol list - arbitrary, but '012...' >> here >> >> 'd g' =. 1 0 + y >> >> a{~ d #.inv i. d^g >> >> ) >> >> >> >> join =: 3 : 0 >> >> : >> >> nx =. #x [ ny =. #y >> >> (ny#x),. (,y)$~ (nx,1) * $y >> >> ) >> >> >> >> NB. join =: ,/@(,"1/) >> >> >> >> NB. Generate all RGFs, each using at least one of each symbol/digit >> 0123...k >> >> representing >> >> NB. (k+1)partitions >> >> NB. Method: let a "basic" RGF for 4 symbols be, eg, 0001002000300, >> >> NB. ie having exactly one of each non-zero >> >> NB. This example has gaps of size 2 3 and 2 again between digits >> 1&2, 2&3, >> >> and 3&[end] respectively >> >> NB. it is the template for many derived RGFs. >> >> NB. A derived RGF is based on a basic RGF with arbitrary >> digits >> >> replacing zeros in the gaps, >> >> NB. subject to added digits not exceeding the left hand >> boundary >> >> of the gap. >> >> NB. eg, the sequence 20003 may have some or all of the 3 >> zeros >> >> replaced by 1 or 2 but not 3 >> >> >> >> NB. 3 helper functions: x join y : x ,/@(,"1/) y, but seems better in >> >> explicit code!? >> >> NB. - concatenates all rows of x with all rows of y >> >> >> >> NB. makeinsert d,g : form a table with g columns >> >> NB. of all possible perms of 0 1 >> 2 ... >> >> d >> >> NB. to yield all suitable >> replacements >> >> for g zeros >> >> >> >> NB. comb - as in stats.ijs, or otherwise, >> according to >> >> taste! >> >> >> >> require'stats' >> >> >> >> rgfMD =: 3 : 0 >> >> : >> >> k =. <: x >> >> n =. y >> >> a =. a. |.~ a. i. '0' NB. symbol list - arbitrary, but '012...' >> here >> >> if. x > n do. NB. special-case impossible partitions >> >> ' '$~ 0, n return. >> >> elseif. x = 1 do. NB. special-case 1-partition >> >> ,: n#{.a return. >> >> elseif. x = 2 do. NB. special-case 2-partition >> >> a{~ (n#2) #: }. i. 2 ^ n-1 return. >> >> elseif. x = n do. NB. special-case n-partition >> >> ,: n{.a return. >> >> end. >> >> c =. >: k comb <:n NB. possible start cols for 1 2 ... k >> >> g =. <: +/\inv"1] c =. c,. n NB. sizes of gaps between starts of >> 1 2 3 >> >> ... for each RGF pattern >> >> a =. a. }.~ a. i. '0' NB. symbol list - arbitrary, but '012...' >> here >> >> out =. ' '$~ 0, n >> >> for_i. i.#c do. NB. loop for each patterns of start cols >> >> gi =. i{g >> >> new =. 1 0$a NB. defer setting initial zeros >> >> for_j. }.i.#gi do. NB. loop over non-zero digits >> >> new=. new,. j{a NB. append next non-zero digit >> >> gj =. j{ gi NB. size of following gap >> >> if. gj do. NB. if size of gap is non-zero, append all >> >> gap-sized sets of 0 1 ... j >> >> new =. new join makeinsert j, gj >> >> end. >> >> end. >> >> out =. out, new join~ a{~ ,: 0{. ~ -{.i{c NB. prepend initial >> zeros >> >> end. >> >> ) >> >> >> >> makeinsert =: 3 : 0 M. >> >> a =. a. }.~ a. i. '0' NB. symbol list - arbitrary, but '012...' >> here >> >> 'd g' =. 1 0 + y >> >> a{~ d #.inv i. d^g >> >> ) >> >> >> >> join =: 3 : 0 >> >> : >> >> nx =. #x [ ny =. #y >> >> (ny#x),. (,y)$~ (nx,1) * $y >> >> ) >> >> >> >> NB. join =: ,/@(,"1/) NB. explicit verb seems better!? >> >> >> >> Cheers, >> >> >> >> Mike >> >> >> >> >> >> >> >> >> >>> On 17/11/2017 18:14, '[email protected]' via Programming >> 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/forum >> s.htm >> >> >> >> >> >> >> >> --- >> >> This email has been checked for viruses by Avast antivirus software. >> >> https://www.avast.com/antivirus >> >> >> >> ---------------------------------------------------------------------- >> >> 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
