Here's a partial solution: it does not factor out permutations of the
pieces. I have some doubts as to how large a problem of this type one
can realistically solve, given that the multinomial coefficients get
so large.
Each partition of n is a vector of length n, whose entries give the
corresponding partition number (1-based). The code works using
breath-first search.
NB. From Dictionary
comb=: 4 : 0
k=. i.>:d=.y-x
z=. (d$<i.0 0),<i.1 0
for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
; z
)
NB. Extend a node
xt1=:4 : 0"1
zindex=.I. 0=y
index=.x comb +/0=y
y+"1 (>:>./y)*(i.#y) e."1 index{zindex
)
NB. Extend a list of nodes
xt=:4 : '; x&xt1&.> <"1 y'
NB. Partition n into p partitions
f=:3 : 0
'n p'=.y
k=.n%p
k&xt^:p ] n $ 0
)
(20000+i.10) { f 12 3
3 2 1 1 1 1 3 2 3 3 2 2
3 2 1 1 1 1 3 3 2 2 2 3
3 2 1 1 1 1 3 3 2 2 3 2
3 2 1 1 1 1 3 3 2 3 2 2
3 2 1 1 1 1 3 3 3 2 2 2
3 3 1 1 1 1 2 2 2 2 3 3
3 3 1 1 1 1 2 2 2 3 2 3
3 3 1 1 1 1 2 2 2 3 3 2
3 3 1 1 1 1 2 2 3 2 2 3
3 3 1 1 1 1 2 2 3 2 3 2
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
