Yes, choice of symbols is a matter of taste or something... Mike Please reply to [email protected]. Sent from my iPad
> On 18 Nov 2017, at 12:36, Raul Miller <[email protected]> wrote: > > Yeah, that's ascii for you - though it doesn't really matter. > > Of course, if that bothers you you could replace > a =. a. }.~ a. i. '0' NB. symbol list - arbitrary, but '012...' > with > a=. ~.;{:@;: ::a:"1 '0',.~a. > > But that's probably not worth the extra millisecond it costs. > > Thanks, > > -- > Raul > > > On Sat, Nov 18, 2017 at 7:01 AM, Erling Hellenäs > <[email protected]> wrote: >> Hi all! >> >> I wondered what would happen when we ran out of digits. >> >> a=:14 parMD 15 >> 1{a >> 01023456789:;<= >> >> Cheers, >> Erling Hellenäs >> >> >>> On 2017-11-17 19: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 >> >> >> >> ---------------------------------------------------------------------- >> 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
