http://www.jsoftware.com/jwiki/Essays/Partitions
Henry Rich > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of > Tirrell, Jordan (Intern) > Sent: Wednesday, July 23, 2008 2:05 PM > To: [email protected] > Subject: [Jprogramming] equal-size partitions > > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
