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), ]

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

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

______________________________________________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