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
┌─────┬─────┐
│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│
└─────┴─────┘
I hope this clarifies.
-----Original Message-----
From: [EMAIL PROTECTED] [mailto:[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
