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/forums.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
