blockmake=: (-@[ {."1&.> ] <@({.,"0 1 }.)"0 1~ 1+])i.
(5 blockmake 4) -: 4 makeblock 5
1
Thanks,
--
Raul
On Fri, Nov 17, 2017 at 1:14 PM, '[email protected]' via
Programming <[email protected]> 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
