[R] Generating all possible partitions

[Gabor Grothendieck]

Just some clarification.  The answer I gave before is interpreted like this:
3 0 0 means the partition of 3 into 3+0+0, 2 1 0 means
the partition of 3 into 2+1+0 and 1 1 1 means the partition
of 3 into 1+1+1.

As pointed out to me privately you asked for only those partitions
that correspond to exactly k groups so it should be modified
like this:

n <- 3; k <- 2
g <- do.call("expand.grid", rep(list(1:n), k)) # cartesian product
f <- function(x) all(diff(x) <= 0) && sum(x) == n
g[apply(g, 1, f), ]

The output in the above case, i.e. n=3, k=2, has only one element which
is 2 1 which means the only partition of 3 into 2 groups is 2+1.

On 11/25/05, Gabor Grothendieck <ggrothendieck at gmail.com> wrote:
> Probably not very fast but the number of partitions of a number,
> also known as the Bell number, grows pretty dramatically so you
> won't be able to use it for large numbers even with an efficient
> implementation (though you could use it for larger numbers than
> the solution here).  The main attribute of this approach is its
> simplicity.   It generates the cartesian product
> { 0, 1, 2, ..., n } ^ n and then picks off the elements that are
> non-increasing and sum to n.
>
> n <- 3
> g <- do.call("expand.grid", rep(list(0:n), n)) # cartesian product
> f <- function(x) all(diff(x) <= 0) && sum(x) == length(x)
> g[apply(g, 1, f), ]
>
>
> On 11/25/05, Ales Ziberna <aleszib at gmail.com> wrote:
> > I have posed this question earlier, however it has probably not been clear
> > enough.
> >
> >
> >
> > My problem is such. I would like to find all possible partitions of a set of
> > n objects into k groups. The ordering of the groups does not matter, only
> > which objects are together matters.
> >
> >
> >
> > For example, there are two possible partitions of 3 objects into 2 groups:
> >
> > 1 1 2
> >
> > 1 2 2
> >
> > By "the labels are not important" I meant that a partition 1 1 2 is
> > identical to the partition 2 2 1.
> >
> >
> > Best regards,
> >
> > Ales Ziberna
> >
> > ______________________________________________
> > R-help at stat.math.ethz.ch mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
> >
>