I think combinations are a better fit than partitions. For example, for n=6 and k=2 (6 objects, 2 "partitions"), using "comb" from http://www.jsoftware.com/help/dictionary/cfor.htm we get:
(6%2) comb 6 0 1 2 0 1 3 0 1 4 0 1 5 0 2 3 0 2 4 0 2 5 0 3 4 0 3 5 0 4 5 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 This counts each "partition" exactly twice, because if 0 1 2 is in a group then automatically 3 4 5 is in the other. $ (6%2) comb 6 20 3 So there are exactly 10 different "partitions". To capture the required property that order within a "partition" and the ordering of the "paritions" do not matter, it's better to describe the problem as follows: divide a set of n objects into k equal-sized subsets. The solutions for n=6 and k=2 are: 0 1 2 3 4 5 0 1 3 2 4 5 0 1 4 2 3 5 0 1 5 2 3 4 0 2 3 1 4 5 0 2 4 1 3 5 0 2 5 1 3 4 0 3 4 1 2 5 0 3 5 1 2 4 0 4 5 1 2 3 ----- Original Message ----- From: Henry Rich <[EMAIL PROTECTED]> Date: Wednesday, July 23, 2008 11:09 Subject: RE: [Jprogramming] equal-size partitions To: 'Programming forum' <[email protected]> > 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? ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
