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
