Re: [R] Generating all possible partitions

From: Ravi Varadhan <rvaradha_at_jhsph.edu>
Date: Sat 26 Nov 2005 - 06:09:38 EST


Isn't Bell number different from the number of partitions, P_n, of a number, n?

Bell number, B_n, is the number of subsets into which a set with "n" elements can be divided. So, B_3 = 5, and B_4 = 15, whereas P_3 = 3, and P_4 = 5. Bell numbers grow much more rapidly than the number of partitions.

Ravi.

> -----Original Message-----
> From: r-help-bounces@stat.math.ethz.ch [mailto:r-help-
> bounces@stat.math.ethz.ch] On Behalf Of Gabor Grothendieck
> Sent: Friday, November 25, 2005 1:10 PM
> To: Ales Ziberna
> Cc: R-help
> Subject: Re: [R] Generating all possible partitions
>
> 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@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@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
> >
>
> ______________________________________________
> R-help@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



R-help@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 Received on Sat Nov 26 06:14:56 2005

This archive was generated by hypermail 2.1.8 : Fri 03 Mar 2006 - 03:41:21 EST