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
