I am currently stumped by what seems to be a natural problem and I think
it is likely someone else has encountered it, or at least knows how to
do it far better than me.
I want all partitions of a given number of objects (say n) into a given
number of equal-size pieces (say k, which divides n).
It is easy to use permutations to do this in small cases, like n=6, k=2:
(([EMAIL PROTECTED] A. i.) 6) {"1 (3#i.2)
But since this permutes non-distinct elements, there are 720 results,
but only 20 are unique. And since a partition is not ordered, 0 0 0 1 1
1 is equivalent to 1 1 1 0 0 0, and so really we reduce to 10 cases.
But the obvious problem comes in because I want to do this many times
for larger numbers. Moving up to only n=12 creates a limit error for me:
([EMAIL PROTECTED] A. i.) 12
There are 479001600=!12 cases here, though if k=3 we would reduce them
to a very reasonable 11550=(!12)%3*(!4)^3 cases.
I could use a loop to go through every permutation and take only the
ones I consider to be unique, but this is a lot of extra computation. It
seems to me that there should be an elegant and quick way to do this in
J, but I cannot figure out what it is.
An Idea:
I was thinking that I could represent one of these partitions by a
matrix where each row represents a segment in the partition, and that
row contains the locations of the objects in that segment.
p=: 4#i.3
> p </. i. # p
0 1 2 3
4 5 6 7
8 9 10 11
If you permute elements only from one row to another and continually
apply /:~ and /:~"1 these correspond exactly to the unique cases I want.
Any ideas on how to do this efficiently?
Thanks,
Jordan Tirrell
[EMAIL PROTECTED]
a.{~74++/\0,37,(}:,(<:&{:))@(],-&])3 _14
a.{~84+0,(((-&2)&{.),}.)(6*3>i.6)&+,~17,,~24
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
