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
<programm...@jsoftware.com> 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, 'mike_liz....@tiscali.co.uk' 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
