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

[(Ted Harding)]

On 09-Dec-05 Ingmar Visser wrote:
> 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

I would be interested in this too! From the name "nkpartitions"
it would seem that this function generates the ways of distributing
n items over k classes; and, in the context of Ales Ziberna's
original query, two such distributions are considered the same
if one can be obtained from the other by permuting classes.

This last consideration, in particular, is not trivial!

Ted.

>> 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
>>
> 
> ______________________________________________
> 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

--------------------------------------------------------------------
E-Mail: (Ted Harding) <Ted.Harding at nessie.mcc.ac.uk>
Fax-to-email: +44 (0)870 094 0861
Date: 09-Dec-05                                       Time: 10:05:13
------------------------------ XFMail ------------------------------