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, '[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
---
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
