[R] Generating all possible partitions

Gabor Grothendieck ggrothendieck at gmail.com
Fri Nov 25 19:09:30 CET 2005


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
>




More information about the R-help mailing list