R help - Dec 2005 - Finding all possible partitions of N units into k classe

See Also 
http://finzi.psych.upenn.edu/R/library/caTools/html/combs.html

Jarek Tuszynski

-----Original Message-----
From: r-help-bounces at stat.math.ethz.ch
[mailto:r-help-bounces at stat.math.ethz.ch] 
Sent: Thursday, December 08, 2005 11:19 AM
To: Ales Ziberna
Cc: R-help
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