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
PLEASE do read the posting guide! http://www.R-project.org/posting-
guide.html
______________________________________________
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

Search Discussions

Discussion Posts

Previous

Follow ups

Related Discussions

Discussion Navigation
viewthread | post
posts ‹ prev | 5 of 7 | next ›
Discussion Overview
groupr-help @
categoriesr
postedNov 25, '05 at 10:13a
activeNov 26, '05 at 8:13a
posts7
users3
websiter-project.org
irc#r

People

Translate

site design / logo © 2018 Grokbase