FAQ
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 at stat.math.ethz.ch [mailto:r-help-
bounces at 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 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
guide.html
______________________________________________
R-help at stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
guide.html

Related Discussions

 view thread | post posts ‹ prev | 5 of 7 | next ›
Discussion Overview
 group r-help categories r posted Nov 25, '05 at 10:13a active Nov 26, '05 at 8:13a posts 7 users 3 website r-project.org irc #r

3 users in discussion

Content

People

Support

Translate

site design / logo © 2018 Grokbase