[R] Generating all possible partitions

[Ales Ziberna]

Thank you all for your answers. Unfortunately, I have realized that my 
example was flawed. There are obviously 3 partitions of 3 objects into 2 
classes:



1 1 2

1 2 1

2 1 1



I would like to emphasize that the numbers are not important, for example, 
we could exchage 1s and 2s or even replace them with a and b.



What did until now is to use the following two functions (the functions are 
at the bottom of the mail):



All.k3.n5.par<- find.all.par(n=5,k=3)

All.k3.n5.par<-remove.double(All.k3.n5.par)



However, this is very time consuming and only suitable for very small n and 
k.



Thank you again for all the answers,



Best refgards,

Ales Ziberna



find.all.par<-function( #suitable for only very small networks and ks 
(complexity is k^n)

            n,         #number of units

            k,         #number of clusters

            only.k.groups=TRUE,  #do we damand that a partition has exactly 
k groups, or are less groups also allowed

            switch.names=TRUE   #should partitions that only differ in group 
names be considert equal (is c(1,1,2)==c(2,2,1))

){

            groups<-rep(list(1:k),n)

            comb<-as.matrix(expand.grid(groups))

            comb<-comb[,dim(comb)[2]:1]

            dimnames(comb)<-NULL

            if(switch.names) comb<-comb[1:(dim(comb)[1]/2),]

            comb<-comb[apply(comb,1,function(x)length(table(x)))>=ifelse(only.k.groups,k,2),]

            return(comb)

}



remove.double<-function(M) #removes duplicated partitios (when rand = 1) 
from matrix M

{

            new.M<-M[1,, drop = FALSE]

            for(i in 2:dim(M)[1]){

                        new<-TRUE

                        for(i2 in 1:dim(new.M)[1])

                        {

                                   if(rand(table(as.numeric(M[i,]),as.numeric(new.M[i2,])))==1)new<-FALSE

                        }

                        if(new) new.M<-rbind(new.M,M[i,])

            }

            return(new.M)

}



#a function used by function "remove.double"

rand<-function (tab) #extracted from function classAgreement from packcage 
'e1071'

{

    n <- sum(tab)

    ni <- apply(tab, 1, sum)

    nj <- apply(tab, 2, sum)

    n2 <- choose(n, 2)

    1 + (sum(tab^2) - (sum(ni^2) + sum(nj^2))/2)/n2

}



----- Original Message ----- 
From: "Gabor Grothendieck" <ggrothendieck at gmail.com>
To: "Ravi Varadhan" <rvaradha at jhsph.edu>
Cc: "Ales Ziberna" <aleszib at gmail.com>; "R-help" <r-help at stat.math.ethz.ch>
Sent: Friday, November 25, 2005 8:16 PM
Subject: Re: [R] Generating all possible partitions


Yes, I just checked on Wikipedia and its as you say.

On 11/25/05, Ravi Varadhan <rvaradha at jhsph.edu> wrote:
> 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 <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
> > >
> >
> > ______________________________________________
> > 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
>