[R] Finding all possible partitions of N units into k classe

[Ingmar Visser]

Can you tell us which package that function is in?
Google on the r-project site nor on the www produced a hit.
best, ingmar

> From: "Ales Ziberna" <aleszib at gmail.com>
> Date: Fri, 9 Dec 2005 09:22:47 +0100
> To: "R-help" <r-help at stat.math.ethz.ch>
> Subject: Re: [R] Finding all possible partitions of N units into k classe
> 
> I would like to thank everybody who replied for their useful suggestions and
> especially the person who (since you replied privately, I do not know if I
> may expose your name or function) provided the "nkpartitions" function, that
> does exactly what I wanted.
> 
> 
> 
> Thank you all again!
> 
> 
> Best,
> 
> Ales Ziberna
> 
> ----- Original Message -----
> From: "Ted Harding" <Ted.Harding at nessie.mcc.ac.uk>
> To: "Ales Ziberna" <aleszib at gmail.com>
> Cc: "R-help" <r-help at stat.math.ethz.ch>
> Sent: Thursday, December 08, 2005 5:19 PM
> Subject: RE: [R] Finding all possible partitions of N units into k classe
> 
> 
> On 08-Dec-05 Ales Ziberna wrote:
>> Dear useRs!
>> 
>> I would like to generate a list of all possible (unique)
>> partitions of N units into k classes. For example, all possible
>> partitions of 4 units into 2 classes are (I hope I have not
>> missed anyone):
>> 
>> 1,1,1,2 (this can be read as {1,2,3},{4})
>> 1,1,2,1
>> 1,2,1,1
>> 2,1,1,1
>> 1,1,2,2
>> 1,2,1,2
>> 1,2,2,1
>> 
>> The partitions 1,1,2,2 and 2,2,1,1 are the same and are
>> therefore not two unique partitions.
> 
> ... which seems to imply that 2,1,1,1 and 1,2,2,2 are the same,
> so I would write your list above as
> 
>> 1,1,1,2 (this can be read as {1,2,3},{4})
>> 1,1,2,1
>> 1,2,1,1
>> 1,2,2,2
>> 1,1,2,2
>> 1,2,1,2
>> 1,2,2,1
> 
> which should be a clue!
> 
> Fix the class to which unit "1" belongs as Class 1. This
> leaves the partitioning of units 2:N, of which there are
> 2^(N-1) except that you want to exclude the case where they
> all go into Class 1. So 2^(N-1) -1.
> 
> So let K = 1:(2^(N-1)-1), and for each k in K make the binary
> representation of k. Say this gives N-1 binary digits
> 
> i1 i2 ... i[N-1]
> 
> (note that none of these will have all binary digits = 0).
> 
> Then assign unit "j+1" to Class 1 if ij = 0, otherwise to
> Class 2.
> 
> However, that is if you want to do it with your bare hands!
> The package combinat contains also the function 'hcube' which
> can be readily adapted to do just that (since it initially
> generates all the 2^N combinations of the above).
> 
> library(combinat)
> ?hcube
> 
> x<-rep(2,4) # for partitions of 4 units into classes {1,2}
> 
> hcube(x,scale=1,transl=0)
> #       [,1] [,2] [,3] [,4]
> #  [1,]    1    1    1    1
> #  [2,]    2    1    1    1
> #  [3,]    1    2    1    1
> #  [4,]    2    2    1    1
> #  [5,]    1    1    2    1
> #  [6,]    2    1    2    1
> #  [7,]    1    2    2    1
> #  [8,]    2    2    2    1
> #  [9,]    1    1    1    2
> # [10,]    2    1    1    2
> # [11,]    1    2    1    2
> # [12,]    2    2    1    2
> # [13,]    1    1    2    2
> # [14,]    2    1    2    2
> # [15,]    1    2    2    2
> # [16,]    2    2    2    2
> 
> ### Note, by following the "2"s, that this is counting in binary
> ### from 0 to 2^N - 1, with "1" for 0 and "2" for 1 and least
> ### significant bit on the left, so it does what is described
> ### above. But we need to manipulate this, so assign it to K:
> 
> K<-hcube(x,scale=1,transl=0)
> 
> ### Now select only thos which assign unit "1" to Class 1:
> 
> K[K[,1]==1,]
> #      [,1] [,2] [,3] [,4]
> # [1,]    1    1    1    1
> # [2,]    1    2    1    1
> # [3,]    1    1    2    1
> # [4,]    1    2    2    1
> # [5,]    1    1    1    2
> # [6,]    1    2    1    2
> # [7,]    1    1    2    2
> # [8,]    1    2    2    2
> 
> of which you need to leave off the first, so, finally:
> 
> N<-4  ### Or general N at this point
> 
> x<-rep(2,N)
> 
> K<-hcube(x,scale=1,transl=0)
> 
> K[K[,1]==1,][-1,]
> #      [,1] [,2] [,3] [,4]
> # [1,]    1    2    1    1
> # [2,]    1    1    2    1
> # [3,]    1    2    2    1
> # [4,]    1    1    1    2
> # [5,]    1    2    1    2
> # [6,]    1    1    2    2
> # [7,]    1    2    2    2
> 
> 
> That looks like it!
> 
> Best wishes,
> Ted.
> 
> 
> --------------------------------------------------------------------
> E-Mail: (Ted Harding) <Ted.Harding at nessie.mcc.ac.uk>
> Fax-to-email: +44 (0)870 094 0861
> Date: 08-Dec-05                                       Time: 16:19:24
> ------------------------------ XFMail ------------------------------
> 
> ______________________________________________
> 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
>