I was going to say that that’s a nice special case and I hadn’t quite got there!
But it misses several cases, eg 01203, 01023 and so on. There are 10 partitions in all. What a pity, Mike Please reply to [email protected]. Sent from my iPad > On 22 Nov 2017, at 22:51, 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]> 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] <javascript:;>. >> Sent from my iPad >> >>> On 22 Nov 2017, at 21:56, Raul Miller <[email protected] >> <javascript:;>> 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] <javascript:;>> 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] <javascript:;>' 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 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
