With length 2 subsets you can do L2ss=: 3 : ';([,@:+ [EMAIL PROTECTED] ,:@])&.>/<@(!*i.@>:)"0 |.}.+:i.x:y'
(L2ss-: ] A.@;"[EMAIL PROTECTED] +:) and L2ss is a lot more efficient. (L2ss-: ] A.@;"[EMAIL PROTECTED] +:)6 1 5 ts'(] A.@;"[EMAIL PROTECTED] +:)6' 0.39404371 13174528 5 ts'L2ss 6' 0.0094924275 2035968 # L2ss 8 2027025 8 ness 16 2027025 However, also L2ss seems to perform exponentially. R.E. Boss > -----Oorspronkelijk bericht----- > Van: [EMAIL PROTECTED] [mailto:programming- > [EMAIL PROTECTED] Namens R.E. Boss > Verzonden: zaterdag 26 juli 2008 18:24 > Aan: 'Programming forum' > Onderwerp: RE: [Jprogramming] equal-size partitions > > cmb=: [:; [:(,.&.><@;\.)/ >:@[EMAIL PROTECTED] > > ep=: 4 : 0 > if. x={:$y do. y > else. > t0=.0,. >: x cmb&<: {:$ y > (t0{"_ 1 y),"1 t1=:x ep (<@<@<"1 t0) {"1 y > end. > ) > > EqPrts=: 4 : '(-y%x)<\"1 ,/"3^:([EMAIL PROTECTED]) (y%x) ep i.y' > > 2 EqPrts 6 > +-----+-----+ > |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| > +-----+-----+ > > > R.E. Boss > > > > -----Oorspronkelijk bericht----- > > Van: [EMAIL PROTECTED] [mailto:programming- > > [EMAIL PROTECTED] Namens Tirrell, Jordan (Intern) > > Verzonden: donderdag 24 juli 2008 0:16 > > Aan: Programming forum > > Onderwerp: RE: [Jprogramming] equal-size partitions > > > > Sorry, I was using a different form of 'partition' than the one on the > > JWiki. I want all ways to separate the objects i.n into k disjoint sets > of > > size n%k (for n,k). Since they are the same size, this is just the > > singular case k$n%k in the JWiki use of partition. > > > > > > > > That is, for the example n=6, k=2, I want all ways to APPLY the > partition > > 3 3 to 6 distinct objects, say 0 1 2 3 4 5. The only ten cases follow. > > > > > > > > ]part=: ((0&=)@{."1#])~.(([EMAIL PROTECTED] A. i.) 6) {"1 (3#i.2) > > > > 0 0 0 1 1 1 > > > > 0 0 1 0 1 1 > > > > 0 0 1 1 0 1 > > > > 0 0 1 1 1 0 > > > > 0 1 0 0 1 1 > > > > 0 1 0 1 0 1 > > > > 0 1 0 1 1 0 > > > > 0 1 1 0 0 1 > > > > 0 1 1 0 1 0 > > > > 0 1 1 1 0 0 > > > > > > > > part </."1 i.6 > > > > ------T-----┐ > > > > │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│ > > > > L-----+------ > > > > > > > > I hope this clarifies. > > > > > > > > > > > > -----Original Message----- > > From: [EMAIL PROTECTED] [mailto:programming- > > [EMAIL PROTECTED] On Behalf Of Henry Rich > > Sent: Wednesday, July 23, 2008 2:09 PM > > To: 'Programming forum' > > Subject: RE: [Jprogramming] equal-size partitions > > > > > > > > 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 > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
