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

[Ales Ziberna]

As to my knowladge, the function is not located in any packages. If you 
wish, I can contact the author and ask him, if he is willing to post the 
function on to the list.

Best,
Ales Ziberna

----- Original Message ----- 
From: "Ingmar Visser" <I.Visser at uva.nl>
To: "Ales Ziberna" <aleszib at gmail.com>; "R-help" <r-help at stat.math.ethz.ch>
Sent: Friday, December 09, 2005 9:56 AM
Subject: Re: [R] Finding all possible partitions of N units into k classe


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
>