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
