[Jprogramming] Partitions

['Mike Day' via Programming]

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