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

From: Ingmar Visser <I.Visser_at_uva.nl>
Date: Fri 09 Dec 2005 - 19:56:47 EST


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@gmail.com>
> Date: Fri, 9 Dec 2005 09:22:47 +0100
> To: "R-help" <r-help@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@nessie.mcc.ac.uk>
> To: "Ales Ziberna" <aleszib@gmail.com>
> Cc: "R-help" <r-help@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@nessie.mcc.ac.uk>
> Fax-to-email: +44 (0)870 094 0861
> Date: 08-Dec-05 Time: 16:19:24
> ------------------------------ XFMail ------------------------------
>
> ______________________________________________
> R-help@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@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 Received on Fri Dec 09 20:03:48 2005

This archive was generated by hypermail 2.1.8 : Fri 03 Mar 2006 - 03:41:35 EST