Roger Hui wrote:
> It is interest to solve some of the derived problems:
> - given a particular division, generate the next (previous) division
Here is a program for generating partitions in lexicographic order. I
am still using uncanonicalized ones, so it gives too many. It will
work on arbitrary sized partitions.
Given a partition p, we want the next. It is obtained by modifying
the suffix starting at last increment in p. For example, the suffix
for 0 1 2 1 3 2 is 1 3 2.
The suffix is now permuted so that
- its first element is minimally incremented
- the rest of the suffix is in non decreasing order
next=:3 : 0
inc=.2 </\ y
if. 0=+/inc do. /:~ y return. end.
last =.inc i: 1
(last {. y), nexts last }. y
)
nexts=:3 : '({.,/:~@:}.) ( y i. <./ @: (#~ (>{.)) y) swap y'
swap=:4 : 'y {~ C. (0,x);<:#y'
next^:(i.20) 0 0 1 1 2 2
0 0 1 1 2 2
0 0 1 2 1 2
0 0 1 2 2 1
0 0 2 1 1 2
0 0 2 1 2 1
0 0 2 2 1 1
0 1 0 1 2 2
0 1 0 2 1 2
0 1 0 2 2 1
0 1 1 0 2 2
0 1 1 2 0 2
0 1 1 2 2 0
0 1 2 0 1 2
0 1 2 0 2 1
0 1 2 1 0 2
0 1 2 1 2 0
0 1 2 2 0 1
0 1 2 2 1 0
0 2 0 1 1 2
0 2 0 1 2 1
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
