I've continued tinkering with ways to derive subsets of Restricted
Generation
Functions equivalent to, ie capable of mapping to, set partitions as
discussed
at length a few weeks ago.
The best I've found recently in dealing with x choices out of n elements
generates
RGFs as columns in a character matrix with n rows and as many columns as
required
to exhaust all possibilities.
A row i then corresponds to the i-th element of each of the RGFs.
It's faster than my previous offering, uses somewhat more space, but
still benefits
from using a character set.
Rather than using x comb n as in my previous posts, it starts with a
2x2 table:
0 0
0 1
and adds n-2 rows, in an explicit loop. I haven't explored the
possibility yet,
but someone might enjoy turning the loop into a verb to the power n-2 (!)
Here's a snapshot of each stage for the (4,6) problem:
t2bnoc/4 6 NB. Top to Bottom NOt using Comb....
+--+
|00|
|01|
+--+
+-----+
|00000|
|00111|
|01012|
+-----+
+--------------+
|00000000000000|
|00001111111111|
|01110001112222|
|10120120120123|
+--------------+
+-----------------------------------+
|00000000000000000000000000000000000|
|00000001111111111111111111111111111|
|01111110000001111112222222222222222|
|10122220122220122220000111122223333|
|22201232201232201230123012301230123|
+-----------------------------------+
+-----------------------------------------------------------------+
|00000000000000000000000000000000000000000000000000000000000000000|
|00000000001111111111111111111111111111111111111111111111111111111|
|01111111110000000001111111112222222222222222222222222222222222222|
|10122222220122222220122222220000000111111122222223333333333333333|
|22201233332201233332201233330123333012333301233330000111122223333|
|33333301233333301233333301233330123333012333301230123012301230123|
+-----------------------------------------------------------------+
The linear output could be modified to a tree-form.
eg the second stage listed above, the one with 3 rows and 5 columns
could be regarded as:
0
/ \
/ \
0 1
/ \ /|\
0 1 0 1 2
which might save some space, but would be less useful for deriving
the set-partitions that this thread has been discussing.
Here's the code - below my sign-off.
It's more verbose than it could be, partly to allow the same special
case treatment of edge cases as before.
Beware line-wrapping - the longest line is nearly 100 characters wide.
Enjoy!
Mike
NB. Longest line:
NB.
=========================================================================================================
NB. "Top to Bottom, NOt using Comb"....
t2bnoc =: 3 : 0
:
k =. <: x
n =. y
a =. x{. 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-1 do. NB. special-case (n-1)-partition
r =. 1 + i.x
|: r ((#-)@[ |."0 1 ;@:((a{~i.)each@[),. # ) r |."0 1 x # ,: a
return.
elseif. x = n do. NB. special-case n-partition
,. n{.a return.
end.
min =. (-n) {. i.x NB. lowest possible entry in each row, if not
present earlier in column
out =. a{~ 0 0,: 0 1 NB. output array - optionally a character array
here
max =. 0 1 NB. highest element, so far, in each column
ins =. 0 NB. preset for max definition below
nins =. 1 NB. number of items to replace each single
entry in a row
for_row. 2}.i.n do. NB. append rows - turn this into a
verb to power n-2 ???
max =. ins >. nins# max NB. update max vector for next row -
reason for preset of max and ins above
minr =. row{min NB. number which must appear in this
row if not before
doins=. minr < maxp1 =. >: max NB. whether to insert a number of
alternative vals, or just a singleton
hi =. (doins * k <. maxp1) + lo =. minr * -. doins NB. bounds for
new values
nins =. hi >:@:- lo NB. number of vals to insert for each
column
ins =. ((] # lo + [: -@(+/\) 0 , }:) + [: i. +/) nins NB. new
row, as integers
NB. equivalent to, but faster than, ins =. ;lo (+ i.) each nins
NB. eg if lo = 0 1 2 1, nins = 2 1 2 3, we get ; 0 1; 1; 2 3;
1 2 3 [not necessarily realistic!]
out =. (ins{a) ,~ nins#"1 out NB. append new row string to expanded
output table
end.
)
---
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
